← 返回题目列表

AtCoder · dp_x

X. 塔

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

分数: 100 点

问题陈述

有 N 块,已编号 1, 2, \ldots, N。 对于每个 i (1 \leq i \leq N),块 i 的权重为 w_i,硬度为 s_i 和值为 v_i.

太郎决定通过选择一些来建造一座塔 N 块并按某种顺序垂直堆叠它们。 这里,塔必须满足以下条件:

  • 对于每个块 i 包含在塔中,其上方堆叠的方块的重量总和不大于 s_i.

找到塔中包含的块的值的最大可能总和。

约束

  • 输入中的所有值都是整数。
  • 1 \leq N \leq 10^3
  • 1 \leq w_i, s_i \leq 10^4
  • 1 \leq v_i \leq 10^9

输入

输入由标准输入按以下格式给出:

N
w_1 s_1 v_1
w_2 s_2 v_2
:
w_N s_N v_N

输出

打印塔中包含的块的值的最大可能总和。


示例输入 1

3
2 2 20
2 1 30
3 1 40

示例输出 1

50

If 块 2, 1 按照从上到下的顺序堆叠起来,这座塔满足条件,总价值为 30 + 20 = 50.


示例输入 2

4
1 2 10
3 1 10
2 4 10
1 6 10

示例输出 2

40

块 1, 2, 3, 4 应按此顺序从上到下堆叠。


示例输入 3

5
1 10000 1000000000
1 10000 1000000000
1 10000 1000000000
1 10000 1000000000
1 10000 1000000000

示例输出 3

5000000000

答案可能不适合 32 位整数类型。


示例输入 4

8
9 5 7
6 2 7
5 7 3
7 8 8
1 9 6
3 3 3
4 1 7
4 5 5

示例输出 4

22

例如,我们应该堆叠块 5, 6, 8, 4 按此顺序从上到下。