题目描述

有 $n$ 个箱子，编号为 $1$ 到 $n$。第 $i$ 号箱子的高度是 $h_i$，重量为 $w_i$，承重能力是 $S_i$。现在要从这 $n$ 个箱子中选若干个，按照任意顺序纵向叠成一个塔。要求每个箱子上面的箱子的总重量不能超过自身的承重能力。问最多可以叠出多高的塔？

输入格式

第 $1$ 行，$1$ 个正整数 $n$。

第 $2$ 到第 $n+1$ 行，每行 $3$ 个正整数 $w_i, s_i, h_i$。

输出格式

输出能叠出的最大高度。

样例输入1

3
2 2 20
2 1 30
3 1 40

样例输出1

50

样例说明1

从下到上，按照第 1、2 号箱子的顺序堆箱子。1 号箱子上面的 2 号箱子的重量是 2，不超过 1 号箱子的承重能力 2。

样例输入2

5
2 4 900000000
2 7 400000000
2 4 300000000
2 2 1000000000
2 6 100000000

样例输出2

2600000000

样例#2说明

答案可能超过 32 位整数类型范围。

样例输入3

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

样例输出3

22

样例#3说明

从下到上，按照第 4、8、6、5 号箱子的顺序堆箱子。第 4 号箱子上面有第 8、6、5 号箱子，总重量等于 8，不超过 4 号箱的承重能力 8。第 8 号箱子上面有第 6、5 号箱子，总重量等于 4，不超过 8 号箱的承重能力 5。第 6 号箱子上面只有第 5 号箱子，重量等于 1，不超过 6 号箱的承重能力 3。

数据范围

20% 数据: $n < 10$

另外有 10% 数据: 所有 $w_i$ 都相等

100% 数据: $2 < n < 1000$; $1 < w_i, s_i < 10^4$; $1 < h_i < 10^9$