题目描述

你有 $n$ 个箱子，编号从 $1$ 到 $n$，每个箱子有三个属性，以第 $i$ 个箱子为例，分别是重量 $w_i$，承重能力 $s_i$，价值 $v_i$。

你想建一座塔，因此需要将一些箱子堆叠起来，但是每个箱子必须满足：这个箱子上面的所有箱子重量和要小于等于这个箱子的承重能力。

定义一个塔的价值为它所用的所有箱子的价值和，问塔的最大价值是多少？

输入格式

第一行一个整数 $n$，表示箱子数量。

接下来 $n$ 行，一行三个整数，用来描述这个箱子的三个属性 $w_i,s_i,v_i$。

输出格式

一行一个整数，表示塔的最大价值。

样例 #1

样例输入 #1

3
2 2 20
2 1 30
3 1 40

样例输出 #1

50

选箱子 $2$ 和箱子 $1$ ，总价值是 $50$ 。

样例 #2

样例输入 #2

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

样例输出 #2

40

直接全选，按顺序放就是合法的选择，总价值为 $40$ 。

样例 #3

样例输入 #3

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

样例输出 #3

5000000000

要注意最后答案有可能超过 $32$ 位整数

样例 #4

样例输入 #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$ 。

提示

对于 $100\%$ 的数据：

• 所有的数据都是整数。
• $1\ \leq\ N\ \leq\ 10^3$
• $1\ \leq\ w_i,\ s_i\ \leq\ 10^4$
• $1\ \leq\ v_i\ \leq\ 10^9$