/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
頭と体からなるロボットがあります。 このロボットには、同時に取り付けられる部品が種類 1, 種類 2,\ldots, 種類 N の N 種類あります。 種類 i\ (1\le i\le N) の部品の重さは W _ i です。 それぞれの部品には、頭に取り付けたときと体に取り付けたときで異なる嬉しさがあります。 種類 i\ (1\le i\le N) の部品を頭に取り付けたときの嬉しさは H _ i 、体に取り付けたときの嬉しさは B _ i です。
ロボットは頭の重さが体の重さより大きいと倒れてしまいます。 ここで、頭の重さおよび体の重さはそれぞれ頭もしくは体に取り付けられた部品の重さの合計とします。
高橋くんは、N 種類の部品をすべて 1 個ずつロボットに取り付けたいと思っています。 ロボットを倒さないように部品を取り付けたときの、すべての部品の嬉しさの合計としてありえる最大値を求めてください。
制約
- 1\le N\le500
- 1\le W _ i\le500\ (1\le i\le N)
- 1\le H _ i\le10 ^ 9\ (1\le i\le N)
- 1\le B _ i\le10 ^ 9\ (1\le i\le N)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N W _ 1 H _ 1 B _ 1 W _ 2 H _ 2 B _ 2 \vdots W _ N H _ N B _ N
出力
ロボットを倒さないように部品を取り付けたときの、すべての部品の嬉しさの合計としてありえる最大値を出力せよ。
入力例 1
3 1 41 59 2 65 35 8 97 93
出力例 1
217
種類 1 と種類 3 の部品を体に、種類 2 の部品を頭に取り付けることで、ロボットを倒さないようにしつつ嬉しさの合計を 217 にすることができます。
ロボットを倒さないように部品を取り付けて嬉しさの合計を 218 以上にすることはできないため、217 を出力してください。
入力例 2
1 1 1000000000 1
出力例 2
1
唯一の部品を体に取り付けないとロボットは倒れてしまいます。 頭にひとつも部品を取り付けなくてもよいことに注意してください。
入力例 3
2 1 1000000000 1 1 1 1000000000
出力例 3
2000000000
頭の重さと体の重さが等しい場合、ロボットは倒れないことに注意してください。
入力例 4
20 483 984529882 299667119 372 428935469 104847758 467 709733529 102461200 421 659244277 110859936 231 786224280 773073478 351 334234040 193222121 119 404159408 772024933 302 519596088 432627257 433 910226244 337833733 184 406236461 530198622 335 465203041 353047747 418 656273464 114923636 482 972364803 329650748 453 748321854 169441643 105 138464898 587159653 401 832952051 506021805 403 810916971 468755944 231 798801044 749313343 292 631278033 556088607 366 567211596 374825770
出力例 4
12091388792
答えが 2 ^ {32} を超える場合があることに注意してください。
Score : 400 points
Problem Statement
There is a robot consisting of a head and a body. This robot has N types of parts that can be attached simultaneously: type 1, type 2,\ldots, type N. The weight of the type i\ (1\le i\le N) part is W _ i. Each part has a different happiness when attached to the head versus when attached to the body. The happiness when the type i\ (1\le i\le N) part is attached to the head is H _ i, and the happiness when attached to the body is B _ i.
The robot falls over if the weight of the head is greater than the weight of the body. Here, the weight of the head and the weight of the body are the sums of the weights of the parts attached to the head or body, respectively.
Takahashi wants to attach all N types of parts to the robot, one of each. Find the maximum possible sum of the happiness of all parts when the parts are attached without causing the robot to fall over.
Constraints
- 1\le N\le500
- 1\le W _ i\le500\ (1\le i\le N)
- 1\le H _ i\le10 ^ 9\ (1\le i\le N)
- 1\le B _ i\le10 ^ 9\ (1\le i\le N)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N W _ 1 H _ 1 B _ 1 W _ 2 H _ 2 B _ 2 \vdots W _ N H _ N B _ N
Output
Print the maximum possible sum of the happiness of all parts when the parts are attached without causing the robot to fall over.
Sample Input 1
3 1 41 59 2 65 35 8 97 93
Sample Output 1
217
By attaching type 1 and type 3 parts to the body and type 2 part to the head, the robot does not fall over and the sum of happiness can be made 217.
It is not possible to attach the parts without causing the robot to fall over and make the sum of happiness 218 or more, so print 217.
Sample Input 2
1 1 1000000000 1
Sample Output 2
1
The robot will fall over if the only part is not attached to the body. Note that it is acceptable to attach no parts to the head.
Sample Input 3
2 1 1000000000 1 1 1 1000000000
Sample Output 3
2000000000
Note that the robot does not fall over if the head and body have equal weights.
Sample Input 4
20 483 984529882 299667119 372 428935469 104847758 467 709733529 102461200 421 659244277 110859936 231 786224280 773073478 351 334234040 193222121 119 404159408 772024933 302 519596088 432627257 433 910226244 337833733 184 406236461 530198622 335 465203041 353047747 418 656273464 114923636 482 972364803 329650748 453 748321854 169441643 105 138464898 587159653 401 832952051 506021805 403 810916971 468755944 231 798801044 749313343 292 631278033 556088607 366 567211596 374825770
Sample Output 4
12091388792
Note that the answer can exceed 2 ^ {32}.