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