2 人解决，2 人已尝试。
2 份提交通过，共有 9 份提交。
8.4 EMB 奖励。
单点时限: 2.0 sec
内存限制: 256 MB
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:
1.reads the credit limits and current credit of every client
2.computes minimal amounts of money in particular currencies sufficient for BBB to end up all the credits,
3.writes the result.
If there are many possible answers, your program should write any of them.
In the first line 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).
Your program should write in the first and only line four nonnegative integers separated by single spaces. They should denote the minimal amounts of money BBB needs in denars, francs, groszes and talers respectively.
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
1 2 0 7 or: 2 0 1 4
2 人解决，2 人已尝试。
2 份提交通过，共有 9 份提交。
8.4 EMB 奖励。