分数: 400 点
问题陈述
有一个机器人,由头部和身体组成。 这个机器人有 N 可同时附加的零件类型:类型 1, 类型 2,\ldots, 类型 N。 类型的权重 i\ (1\le i\le N) 部分是 W _ i。 每个部分都有不同的 幸福 连接到头部时与连接到身体时。 幸福时的类型 i\ (1\le i\le N) 部分附在头部是 H _ i,附着在身体上的幸福是 B _ i.
如果头部重量大于身体重量,机器人就会摔倒。 这里,头部的重量和身体的重量分别是附接到头部或身体的部件的重量之和。
高桥想要附上所有 N 机器人的零件类型,每种一个。 求当零件连接起来不会导致机器人翻倒时,所有零件的幸福感的最大可能总和。
约束
- 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}.