Polish version    English version  
  O olimpiadzie -> Zadania -> II OI 1994/1995


 Aktualności
 O olimpiadzie
O olimpiadzie
Zadania
I OI 1993/1994
II OI 1994/1995
III OI 1995/1996
IV OI 1996/1997
V OI 1997/1998
VI OI 1998/1999
VII OI 1999/2000
VIII OI 2000/2001
IX OI 2001/2002
X OI 2002/2003
XI OI 2003/2004
XII OI 2004/2005
XIII OI 2005/2006
XIV OI 2006/2007
XV OI 2007/2008
Archiwum zadań
Ankieta OI
 Komitety
 XVIII OI 2010/2011
 Historia OI
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
Ten dokument nie jest dostępny w polskiej wersji językowej.

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.

Task

Write a program that:
  • 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 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.

Output

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.

Example

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:

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.




Wersja do druku