问题陈述

有 $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$

输出

打印塔中各图块价值的最大和。

3
2 2 20
2 1 30
3 1 40

50

如果按照从上到下的顺序堆叠图块 $2, 1$ ，这座塔将满足条件，总值为 $30 + 20 = 50$ 。

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

40

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

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

5000000000

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

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

22

例如，我们应该按照从上到下的顺序堆叠区块 $5, 6, 8, 4$ 。

来源

https://atcoder.jp/contests/dp/tasks/dp_x