Niebieskie ksi.eczki
II Olympiad in Informatics 1994/1995

Task: MUD
Author: Andrzej Walat
Mudstock Bis

II stage contest  

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 (kl), 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.


Write a program that:

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.


In the first line of the text file MUD.IN there are two integers: the number of railway lines l (1 <= l < 350) and the number of the members living in the capital of the country m (0 <= m < 100).

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.


The first line of the file MUD.OUT should contain the minimal total cost of all the association members' trip by train back home from the festival. The second line should contain the coordinates of the settlement the festival should be organized in.


The network presented in the picture

a railway network

is described by the following file MUD.IN:
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:

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.