Synchrophasotron

题意翻译

### 题目描述 对于一些实验，小佩佳需要一个同步调速器。 他已经拿到了设备，剩下的就是设置燃料供应。 燃料通过一个节点系统，编号从 $1$ 到 $n$ 并通过管道连接。管道的链接只会从编号较小的每个节点到编号较大的每个节点。燃料只能从编号较小的节点流向编号较大的节点。任何数量的燃料都可以通过第一个节点进入，最后一个节点直接连接到同步调速器。每个管道都具有三个信息：应该通过它的最小燃料量、可能通过它的最大燃料量以及管道激活的成本。如果 $c_{i,j}$ 个燃料单位（ $c_{i,j}>0$ ）从节点 $i $ 流到节点 $j$ ，它将花费 $a_{i,j}+c_{i,j}^{2}$ 图格里克（ $a_{i,j}$ 是 管道激活的成本），如果燃料不流过管道，则不需要任何费用。每个管道只能流过整数个单位的燃料。 对管道最小和最大燃料容量的限制是持续的，而不仅仅是在它处于活动状态时。你可以假设管道是活动的，当且仅当通过它的流量严格大于零时。 小佩佳不希望管道系统过载，因此他想找到进入第一个节点后可以到达同步调速器的最小燃料量。再加上他想给赞助商留下深刻印象，所以每条管道的燃料所需要支付的金额必须尽可能大。 注：图格里克是蒙古货币单位。 ### 输入格式 第一行包含整数 $n$ ($2 \le n \le 6$)，表示节点数。 接下来的 $\frac{n(n-1)}{2}$ 行中的每一行都包含五个描述管道的整数 $s,f,l,h,a$ — 管道的第一个节点，管道的第二个节点，可以流过管道的最小和最大燃料量以及激活成本。 ( $1 \le s<f \le n,0 \le l \le h \le 5,0 \le a \le 6$ )。 可以保证对于每一对具有不同编号的节点，在输入中描述的它们之间将恰好有一个管道。 ### 输出格式 在第一行输出两个空格分隔的数字：可以流入同步调速器的最小可能燃料量，以及为了使该燃料量到达同步调速器而需要支付的最大可能总和。 如果没有足够的燃料可以到达同步调速器，输出 `-1 -1` 。 流入同步调速器的燃料量不一定是正数。如果每个管道的最小约束等于零，则它可能等于零。 ### 样例解释 在第一个样例中，我们可以将 $1$ 个或 $2$ 个单位的燃料从节点 $1$ 传递到节点 $2$。最小可能数量为 $1$，其成本为 $a_{1,2}+1^{2}=4.$ 在第二个测试中，你最多可以从节点 $1$ 向节点 $2$ 传递 $2$ 个单元，并且必须从节点 $2$ 向节点 $3$ 传递至少 $3$ 个单元。这是不可能的。

题目描述

For some experiments little Petya needs a synchrophasotron. He has already got the device, all that's left is to set the fuel supply. Fuel comes through a system of nodes numbered from $ 1 $ to $ n $ 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 $ c_{ij} $ units of fuel ( $ c_{ij}&gt;0 $ ) flow from node $ i $ to node $ j $ , it will cost $ a_{ij}+c_{ij}^{2} $ tugriks ( $ a_{ij} $ is the cost of pipe activation), and if fuel doesn't flow through the pipe, it doesn't cost anything. Only integer number of units of fuel can flow through each pipe. Constraints on the minimal and the maximal fuel capacity of a pipe take place always, 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. Petya doesn't 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.

输入输出格式

输入格式

First line contains integer $ n $ ( $ 2<=n<=6 $ ), which represents the number of nodes. Each of the next $ n(n-1)/2 $ lines contains five integers $ s,f,l,h,a $ 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. ( $ 1<=s&lt;f<=n,0<=l<=h<=5,0<=a<=6 $ ). It is guaranteed that for each pair of nodes with distinct numbers there will be exactly one pipe between them described in the input.

输出格式

Output 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 "-1 -1". The 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.

输入输出样例

输入样例 #1

2
1 2 1 2 3

输出样例 #1

1 4

输入样例 #2

3
1 2 1 2 3
1 3 0 0 0
2 3 3 4 5

输出样例 #2

-1 -1

输入样例 #3

4
1 2 0 2 1
2 3 0 2 1
1 3 0 2 6
1 4 0 0 1
2 4 0 0 0
3 4 2 3 0

输出样例 #3

2 15

输入样例 #4

3
1 2 0 2 1
1 3 1 2 1
2 3 1 2 1

输出样例 #4

2 6

说明

In 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 $ a_{12}+1^{2}=4 $ . In 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. In the third test, the minimum possible amount is 2. You can pass each unit of fuel through two different paths: either 1->2->3->4 or 1->3->4. If you use the first path twice, it will cost $ a_{12}+2^{2}+a_{23}+2^{2}+a_{34}+2^{2} $ =14. If you use the second path twice, it will cost $ a_{13}+2^{2}+a_{34}+2^{2} $ =14. However, if you use each path (allowing one unit of fuel go through pipes 1->2, 2->3, 1->3, and two units go through 3->4) it will cost $ a_{12}+1^{2}+a_{23}+1^{2}+a_{13}+1^{2}+a_{34}+2^{2} $ =15 and it is the maximum possible cost. Also note that since no fuel flows from node 1 to node 4, activation cost for that pipe is not added to the answer.