Description

有 $N$ 个砖块，编号为 $1,2,…,N$。对于每个 $i(1≤i≤N)$ ，块 $i$ 的重量为 $w_i$，坚固性 $​s_i$ 和价值 $v_i$​.

光头强决定从 $N$ 个砖块中选择一些，并按照一定的顺序竖直堆叠，从而建造一座塔。在此，塔架必须满足以下条件：

• 对于塔中包含的每一砖块 $i$，其上方堆叠的砖块的重量总和不大于 $s_i$​.

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

Input

输入格式如下：

$N\\w_1​\ s_1​\ v_1​\\w_2\ ​s_2\ ​v_2\\​:\\w_N\ ​s_N​\ v_N​$​

输入中的所有值都是整数。

$1≤N≤10^3\\1≤w_i​,s_i​≤10^4\\1≤v_i​≤10^9$。

Output

输出光头强能搭建的塔中包含块的价值和的最大值。

Samples

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。