{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\nCompany A wants to transport as many goods as possible from city \u003cvar\u003eS\u003c/var\u003e to city \u003cvar\u003eT\u003c/var\u003e. So they ask company B to do the transportation. There are \u003cvar\u003en\u003c/var\u003e cities here in the problem and there are directed roads from cities \u003cvar\u003ei\u003c/var\u003e to city \u003cvar\u003ej\u003c/var\u003e with capacity \u003cvar\u003ec\u003csub\u003eij\u003c/sub\u003e\u003c/var\u003e.\n\u003c/p\u003e\n\u003cp\u003e\nAfter a long negotiation, A and B reach a consensus that A first decide how to transport the goods (Of course under the condition that most goods are transported and that the quantity transported in each road cannot exceed the capacity) and then B can assign non-negative integer unit transportation costs to each road such that the total unit transportation costs in all roads sum to \u003cvar\u003eP\u003c/var\u003e. So the money A has to pay is the sum of costs of all roads while the cost of a certain road is the quantity transported (assigned by A) multiplied by the unit transportation cost (assigned by B). Notice that since the goods are not divisible, the quantity transported for each road should be a non-negative integer.\n\u003c/p\u003e\n\u003cp\u003e\nOf course A wants to minimize the cost and B want to maximize the cost. So you are to work out what the total cost will be?\n\u003c/p\u003e\n\u003cp\u003e\nTo make the problem more fun, you should also work out the total cost that A wants to maximize the cost while B wants to minimize it and other conditions keep the same.\n\u003c/p\u003e\n\u003ch4\u003eInput\u003c/h4\u003e\n\u003cp\u003e\nThere are multiple test cases. The first line of the input is an integer \u003cvar\u003eT\u003c/var\u003e ≈ 100 indicating the number of test cases.\n\u003c/p\u003e\n\u003cp\u003e\nFor each test case, the first line contains 5 integers \u003cvar\u003en, m, S, T, P\u003c/var\u003e (2 ≤ \u003cvar\u003en\u003c/var\u003e ≤ 500, 0 ≤ \u003cvar\u003em\u003c/var\u003e ≤ 10000, 0 ≤ \u003cvar\u003eS, T\u003c/var\u003e \u0026lt; n, 0 ≤ \u003cvar\u003eP\u003c/var\u003e ≤ 100000). The next \u003cvar\u003em\u003c/var\u003e lines describe the roads between cities. In each of the \u003cvar\u003em\u003c/var\u003e lines, 3 integers \u003cvar\u003eu, v, c\u003c/var\u003e (0 ≤ \u003cvar\u003eu, v\u003c/var\u003e, 1 ≤ \u003cvar\u003ec\u003c/var\u003e ≤ 100000) are given indicating a road from \u003cvar\u003eu\u003c/var\u003e to \u003cvar\u003ev\u003c/var\u003e with capacity \u003cvar\u003ec\u003c/var\u003e.\n\u003c/p\u003e\n\u003ch4\u003eOutput\u003c/h4\u003e\n\u003cp\u003e\nFor each test case, output one line with two integers. The first is the total cost that A wants to minimize and B wants to maximize, the second is the total cost that A wants to maximize and B wants to minimize.\n\u003c/p\u003e\n\u003ch4\u003eSample\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\n5 5 0 4 1\n0 3 1\n0 2 1\n3 1 1\n2 1 1\n1 4 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\u003ch4\u003eHint\u003c/h4\u003e\n\u003cp\u003e\nA can assign the transported quantity in roads to (1, 0, 1, 0, 1) or (0, 1, 0, 1, 1) in the order as the input. Both of the assignment can transport 1 unit of goods.\n\u003c/p\u003e\n\u003cp\u003e\nSo in the first situation, B can assign 1 unit cost to a road that transport 1 unit of goods and 0 to other roads. The total cost is 1. In the second situation, B can assign 1 unit cost to a road that transport 0 units of goods and 0 to other roads. The total cost is 0.\n\u003c/p\u003e\n"}}]}