The authorities of the Holypolygons association, to celebrate the tenth anniversary of the memorable first rally of its members on the common of Mudstock, have decided to organize a grand festival Mudstock Bis.

The members of the association live in many small settlements of Holypolyland lying along l railway lines (where 1 <= l < 350) numbered by successive integers from 1 to l. No line length exceeds 500 km. All the lines start in the capital and run radially from the capital to the provinces. Those lines do not cross. Each settlement except the capital lies on exactly one line. There is a positive number of settlements, not greater than 100, along each line. The number of the association's members in one settlement also does not exceed 100.

Each settlement (not being the capital) is unambiguously identified by a pair of coordinates (k, l), where k is the number of the line it lies on, and n is the number of the settlement on the line. The settlements on each line are numbered successively from the capital. We assume the capital (which is the beginning of every line) has the coordinates (0, 0).

The authorities of the association fund a train ticket for the trip back home from the festival to every member. The price of the ticket equals the number of kilometres travelled. There has arisen the problem where the festival should be organized to minimize the cost of the railway trip back home of all the association's members.

Task

• reads from the file MUD.IN data describing the railway network: the number of railway lines, the number of the association's members living in the capital, and for every settlement - the number of members living there and the length of the railway line segment from that settlement to the nearest station towards the capital,
• finds a settlement the festival should be organized in to minimize the cost of the railway trip back home of all the participants (the association's members).
• computes this minimal total cost of the railway trips,
• writes the results in the text file MUD.OUT.

If for many settlements the total costs of all the association's members railway trip back home from those settlements are minimal, then your program should find only one such a settlement.

Input

In the following l lines of the file there are descriptions of the railway lines of successive numbers from 1 to l. Each description has a form of a sequence of integers separated by single spaces.

First, there is a positive number of settlements lying on the given line (not counting the capital). Each consecutive pair of numbers comprises: a positive distance of the successive settlement on the given line from the closest settlement towards the capital and a nonnegative number of the association's members living in this settlement. The last number of each description is directly followed by end-of-line character.

The data in the file JED.IN are written correctly, and your program need not verify that.

Output

Example

3 12
2 2 3 2 3
3 3 2 2 0 2 3
3 3 4 1 3 2 3

In this case one should write the following in the file MUD.OUT:

87
0 0

Your program should look for the file MUD.IN in the current directory and create the file MUD.OUT also in the current directory. The source file containing the program written by you should be named MUD.???, where ??? are substituted by at most three-letter abbreviation of the programming language used. The same program in an executable form should be written in a file MUD.EXE.