Polish version    English version  
 


 News
 About Olympic
 History of OI
 OI books
 National team
 Olympic camps
 Photo gallery
 Links
 SIO
 MAIN
Niebieskie ksi.eczki
VIII Olimpiada Informatyczna 2000/2001

Task: BAN
Author: Marcin Kubica
Bank

III Stage contest, the second day  

There are four currencies in Byteland. These are: denary, frank, grosz and taler. They are not convertible (i.e. one cannot exchange one currency into another) and this is a serious disadvantage for the inhabitants of Byteland. The Byteland Bank of Business (short BBB), due to mistake between currencies, has faced the view of bankruptcy. It had made several contracts on giving credits. All of the contracts are of the following form:

  • the contract defines credit limit in every official currency of Byteland,
  • the client, whenever he wants, may ask BBB for the credit of some specified amount of money in each currency; BBB is not obliged to stick to any time limits when preparing money for the client but, as far as the client doesn't exceed his credit limit in any currency, sooner or later the money must be paid to the client,
  • the client, who didn't use all of his credit limit, may apply for another credit,
  • finally the client gives back all the money he had borrowed; there is no time limit for him to do it, but sooner or later he must give the money back,
  • the client doesn't have to use all his credit limit,
  • for simplicity we assume that clients don't pay neither interest nor commission.

BBB does not have enough money to fulfill all its clients needs, whereas no client will pay back his credit before he gets all the money he needs. BBB asked The Byteland National Bank (short BNB) for help. BNB agreed to help BBB, but requested the detailed report on minimal amount of money in each currency sufficient for BBB to make every client pay back his credit. The experts from BBB discovered that there are many possible solutions for the problem (see example). BNB replied that they are interested in any of them. BNB requests four integers - the amount of money in each official currency of Byteland that all together would suffice BBB to make every client give back his credit, but if BBB would have 1 less in any of the currencies and the same amount in the remaining currencies it would be not enough to be sure BBB can end up all the credits.

Task

Write a program which:

  • reads the credit limits and current credit of every client from the file BAN.IN
  • computes minimal amounts of money in particular currencies sufficient for BBB to end up all the credits,
  • writes the result to the file BAN.OUT.

If there are many possible answers, your program should write any of them.

Input

In the first line of the text file BAN.IN there is written one positive integer n equal to the number of clients, 1<=n<=8 000. The clients are numbered from 1 to n. In each of the following n lines there are written eight nonnegative integers. In the (i+1)-th line (i = 1,...,n) there are written integers mi,1,mi,2,mi,3,mi,4,wi,1,wi,2,wi,3,wi,4, (0<=wi,j<=mi,j<=50 000, for j=1,...,4). Integers mi,j and wi,j denote respectively credit limit and current credit of client number i in: denars (j=1), francs (j=2), groszes (j=3) and talers (j=4).

 

Output

Your program should write in the first and only line of the text file BAN.OUT four nonnegative integers separated by single spaces. They should denote the minimal amounts of money BBB needs in denars, francs, groszes and talers respectively.

 

Example

For the input file BAN.IN:

4
3 2 1 2 0 2 0 1
2 4 1 8 1 2 1 1
3 2 0 3 1 0 0 1
3 0 1 2 1 0 0 1

the correct answer might be the text file BAN.OUT:

1 2 0 7
			

or:

2 0 1 4



Print friendly version