分数: 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 按此顺序从上到下。