问题描述

有 $N$ 个块，编号为 $1, 2, \ldots, N$。对于每个 $i$ ($1 \leq i \leq N$)，块 $i$ 的重量为 $w_i$，坚固度为 $s_i$，价值为 $v_i$。

Taro 决定通过选择一些 $N$ 个块并按某种顺序将它们垂直堆叠起来来构建一个塔。在这里，塔必须满足以下条件：

• 每个包含在塔中的块，其上方堆叠的块的重量之和不超过 $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

如果顺序从上到下堆叠块 $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$。