CF68C.Synchrophasotron

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 > 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.

小Petya在进行某些实验时需要一台同步相位加速器（synchrophasotron）。他已获得该设备，目前仅需设定燃料供给系统。燃料经由一套编号为 $1$ 至 $n$ 的节点网络输送，节点之间通过管道连接。所有管道均从编号较小的节点指向编号较大的节点；即对任意 $i < j$，均存在一条从节点 $i$ 到节点 $j$ 的管道。燃料只能沿编号递增方向流过管道。任意数量的燃料均可从第一个节点（节点 $1$）注入，而最后一个节点（节点 $n$）则直接与同步相位加速器相连。

已知每条管道具有三个属性：其最小燃料流量、最大燃料流量，以及管道启用成本。若从节点 $i$ 到节点 $j$ 有 $c_{ij}$ 单位燃料流过（$c_{ij} > 0$），则需花费 $a_{ij} + c_{ij}^2$ 图格里克（tugriks）（其中 $a_{ij}$ 为该管道的启用成本）；若无燃料流过该管道，则不产生任何费用。每条管道中流动的燃料量必须为整数。

管道的最小与最大流量约束始终生效，无论该管道是否被启用。可假定：当且仅当管道中流量严格大于零时，该管道被视为“启用”。

Petya 不希望管道系统过载，因此他希望找出能从第一个节点注入、并最终抵达同步相位加速器的最小总燃料量。此外，为了给赞助商留下深刻印象，他还希望使燃料流经所有管道所需支付的总费用尽可能大。

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 < 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.

第一行包含一个整数 $n$（$2 \leq n \leq 6$），表示节点的数量。接下来的 $\frac{n(n-1)}{2}$ 行，每行包含五个整数 $s,\,f,\,l,\,h,\,a$，用于描述一条管道：分别为该管道的起始节点、终止节点、该管道允许通过的燃料最小流量与最大流量，以及启用该管道的成本（即激活成本）。其中满足 $1 \leq s < f \leq n$，$0 \leq l \leq h \leq 5$，$0 \leq a \leq 6$。保证对于任意两个编号不同的节点，输入中恰好存在一条连接它们的管道。

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.

第一行输出两个用空格分隔的数字：能够流入同步相位器（synchrophasotron）的燃料最小可能量，以及为使该燃料量到达同步相位器所需支付的最大总金额。若没有任何燃料量能够到达同步相位器，则输出 -1 -1。

流入同步相位器的燃料量未必为正；若每条管道的最小流量约束均为零，则该流量可等于零。

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 + 12 = 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 + 22 + _a_23 + 22 + _a_34 + 22=14. If you use the second path twice, it will cost _a_13 + 22 + _a_34 + 22=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 + 12 + _a_23 + 12 + _a_13 + 12 + _a_34 + 22=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.

在第一个测试用例中，我们可以从节点 1 向节点 2 传输 1 或 2 单位的燃料。最小可能传输量为 1，其花费为 $a_{12} + 1^2 = 4$。

在第二个测试用例中，从节点 1 到节点 2 最多可传输 2 单位燃料，而从节点 2 到节点 3 至少需传输 3 单位燃料。这是不可能实现的。

在第三个测试用例中，最小可能传输量为 2。每单位燃料均可通过两条不同路径传输：路径一为 $1 \to 2 \to 3 \to 4$，路径二为 $1 \to 3 \to 4$。若两次均使用路径一，则花费为 $a_{12} + 2^2 + a_{23} + 2^2 + a_{34} + 2^2 = 14$；若两次均使用路径二，则花费为 $a_{13} + 2^2 + a_{34} + 2^2 = 14$。然而，若两条路径各使用一次（即：1 单位燃料经管道 $1 \to 2$、$2 \to 3$ 和 $1 \to 3$，2 单位燃料经管道 $3 \to 4$），则花费为 $a_{12} + 1^2 + a_{23} + 1^2 + a_{13} + 1^2 + a_{34} + 2^2 = 15$，此为可能的最大花费。

还需注意：由于没有燃料从节点 1 流向节点 4，该管道的启用成本不计入答案。