Polish version    English version  
  History of OI -> VII OI 1999/2000 -> Problems


 News
 About Olympic
 History of OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
Stage III - results
Stage II - results
Stage I - results
Problems
Regulations
Organization
Hints
Schedule
Stats
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 OI books
 National team
 Olympic camps
 Photo gallery
 Links
 SIO
 MAIN
Niebieskie ksi.eczki
VII Olimpiada Informatyczna 1999/2000

Task: PRO
Author: Tomasz Waleń
Promotion

III stage contest  

Great Bytelandish net of supermarkets asked you for writing a program simulating costs of the promotion being prepared.

The promotion has to obey the following rules:

  • A customer, who wants to participate in the promotion, writes on the bill, paid by himself, his personal details and throws it to a special ballot box.
  • At the end of every day of the promotion, two bills are taken out from the ballot box:
    • the first bill amounting to the greatest sum is chosen,
    • then the bill amounting to the least sum is chosen;
    The customer, who has paid the greatest bill, gets a money prize equal to the difference between the sum on his bill and the sum on the bill amounting to the least sum.
  • To avoid multiple prizes for one purchase, both bills selected accordingly to the above rules, do not return to the ballot box, but all remaining bills still participate in promotion.

Turnovers of the supermarket are very big, thus an assumption can be made, that at the end of every day, before taking out bills amounting to the greatest and the least sum, there are at least 2 bills in the ballot box.

Your task is to compute on the basis of information about prices on bills thrown to the ballot box on each day of promotion, what will be the total cost of prizes during the whole promotion.

Task

Write a program, which:

  • reads from the text file PRO.IN a list of prices on bills thrown to the ballot box on each day of the promotion,
  • computes the total cost of prizes paid in consecutive days of promotion,
  • writes the result to the text file PRO.OUT.

Input

The first line of the text file PRO.IN contains one positive integer n, where 1 <= n <= 5000, which is the duration of promotion in days.

Each of the next n lines consists of a sequence of non-negative integers separated by single spaces. Numbers in the (i+1)-th line of the file represent prices on bills thrown to the ballot box on the i-th day of promotion. The first integer in the line is k, 0 <= k <= 10^5, the number of bills from the day, and the next k numbers are positive integers standing for the prices on bills; none of these numbers is greater than 10^6.

The total number of bills thrown to the ballot box during the whole promotion does not exceed 10^6.

Output

The text file PRO.OUT should contain exactly one integer, which is equal to the total cost of prizes paid during the whole promotion.

Example

For the input file PRO.IN:
5
3 1 2 3
2 1 1
4 10 5 5 1
0
1 2
the correct answer is the output file PRO.OUT
19



Print friendly version