{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eFor some experiments little Petya needs a synchrophasotron. He has already got the device, all that\u0027s left is to set the fuel supply. Fuel comes through a system of nodes numbered from \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e and connected by pipes. Pipes go from every node with smaller number to every node with greater number. Fuel can only flow through pipes in direction from node with smaller number to node with greater number. Any amount of fuel can enter through the first node and the last node is connected directly to the synchrophasotron. It is known that every pipe has three attributes: the minimum amount of fuel that should go through it, the maximum amount of fuel that can possibly go through it and the cost of pipe activation. If \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003eij\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e units of fuel (\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003eij\u003c/i\u003e\u003c/sub\u003e \u0026gt; 0\u003c/span\u003e) flow from node \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e to node \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/span\u003e, it will cost \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003eij\u003c/i\u003e\u003c/sub\u003e + \u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003eij\u003c/i\u003e\u003c/sub\u003e\u003csup class\u003d\"upper-index\"\u003e2\u003c/sup\u003e\u003c/span\u003e tugriks (\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003eij\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e is the cost of pipe activation), and if fuel doesn\u0027t flow through the pipe, it doesn\u0027t cost anything. Only integer number of units of fuel can flow through each pipe.\u003c/p\u003e\u003cp\u003eConstraints on the minimal and the maximal fuel capacity of a pipe take place \u003cspan class\u003d\"tex-font-style-bf\"\u003ealways\u003c/span\u003e, not only if it is active. You may assume that the pipe is active if and only if the flow through it is strictly greater than zero.\u003c/p\u003e\u003cp\u003ePetya doesn\u0027t want the pipe system to be overloaded, so he wants to find the minimal amount of fuel, that, having entered the first node, can reach the synchrophasotron. Besides that he wants to impress the sponsors, so the sum of money needed to be paid for fuel to go through each pipe, must be as big as possible.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eFirst line contains integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e2 ≤ \u003ci\u003en\u003c/i\u003e ≤ 6\u003c/span\u003e), which represents the number of nodes. Each of the next \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e(\u003ci\u003en\u003c/i\u003e - 1) / 2\u003c/span\u003e lines contains five integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e, \u003ci\u003ef\u003c/i\u003e, \u003ci\u003el\u003c/i\u003e, \u003ci\u003eh\u003c/i\u003e, \u003ci\u003ea\u003c/i\u003e\u003c/span\u003e that describe pipes — the first node of the pipe, the second node of the pipe, the minimum and the maximum amount of fuel that can flow through the pipe and the the activation cost, respectively. (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003es\u003c/i\u003e \u0026lt; \u003ci\u003ef\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e, 0 ≤ \u003ci\u003el\u003c/i\u003e ≤ \u003ci\u003eh\u003c/i\u003e ≤ 5, 0 ≤ \u003ci\u003ea\u003c/i\u003e ≤ 6\u003c/span\u003e). It is guaranteed that for each pair of nodes with distinct numbers there will be exactly one pipe between them described in the input.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eOutput in the first line two space-separated numbers: the minimum possible amount of fuel that can flow into the synchrophasotron, and the maximum possible sum that needs to be paid in order for that amount of fuel to reach synchrophasotron. If there is no amount of fuel that can reach synchrophasotron, output \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e-1 -1\u003c/span\u003e\".\u003c/p\u003e\u003cp\u003eThe amount of fuel which will flow into synchrophasotron is not neccessary positive. It could be equal to zero if the minimum constraint of every pipe is equal to zero.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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\u003e2\n1 2 1 2 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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\u003e3\n1 2 1 2 3\n1 3 0 0 0\n2 3 3 4 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e-1 -1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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\u003e4\n1 2 0 2 1\n2 3 0 2 1\n1 3 0 2 6\n1 4 0 0 1\n2 4 0 0 0\n3 4 2 3 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2 15\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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\u003e3\n1 2 0 2 1\n1 3 1 2 1\n2 3 1 2 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2 6\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first test, we can either pass 1 or 2 units of fuel from node 1 to node 2. The minimum possible amount is 1, it costs \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e12\u003c/sub\u003e + 1\u003csup class\u003d\"upper-index\"\u003e2\u003c/sup\u003e \u003d 4\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eIn the second test, you can pass at most 2 units from node 1 to node 2, and at you have to pass at least 3 units from node 2 to node 3. It is impossible.\u003c/p\u003e\u003cp\u003eIn the third test, the minimum possible amount is 2. You can pass each unit of fuel through two different paths: either 1-\u0026gt;2-\u0026gt;3-\u0026gt;4 or 1-\u0026gt;3-\u0026gt;4. If you use the first path twice, it will cost \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e12\u003c/sub\u003e + 2\u003csup class\u003d\"upper-index\"\u003e2\u003c/sup\u003e + \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e23\u003c/sub\u003e + 2\u003csup class\u003d\"upper-index\"\u003e2\u003c/sup\u003e + \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e34\u003c/sub\u003e + 2\u003csup class\u003d\"upper-index\"\u003e2\u003c/sup\u003e\u003c/span\u003e\u003d14. If you use the second path twice, it will cost \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e13\u003c/sub\u003e + 2\u003csup class\u003d\"upper-index\"\u003e2\u003c/sup\u003e + \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e34\u003c/sub\u003e + 2\u003csup class\u003d\"upper-index\"\u003e2\u003c/sup\u003e\u003c/span\u003e\u003d14. However, if you use each path (allowing one unit of fuel go through pipes 1-\u0026gt;2, 2-\u0026gt;3, 1-\u0026gt;3, and two units go through 3-\u0026gt;4) it will cost \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e12\u003c/sub\u003e + 1\u003csup class\u003d\"upper-index\"\u003e2\u003c/sup\u003e + \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e23\u003c/sub\u003e + 1\u003csup class\u003d\"upper-index\"\u003e2\u003c/sup\u003e + \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e13\u003c/sub\u003e + 1\u003csup class\u003d\"upper-index\"\u003e2\u003c/sup\u003e + \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e34\u003c/sub\u003e + 2\u003csup class\u003d\"upper-index\"\u003e2\u003c/sup\u003e\u003c/span\u003e\u003d15 and it is the maximum possible cost.\u003c/p\u003e\u003cp\u003eAlso note that since no fuel flows from node 1 to node 4, activation cost for that pipe is not added to the answer.\u003c/p\u003e"}}]}