← 返回题目列表

AtCoder · abc431_d

G. 机器人定制

中文机器翻译题面 查看原题

分数: 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}.