These problems are from the atcoder DP contest, and were transferred onto DMOJ. All problem statements were made by several atcoder users. As there is no access to the test data, all data is randomly generated. If there are issues with the statement or data, please contact Rimuru or Ninjaclasher on slack.

There are ~N~ blocks, numbered ~1, 2, \ldots, N~. For each ~i\ (1 \le i \le N)~, Block ~i~ has a weight of ~w_i~, a solidness of ~s_i~, and a value of ~v_i~.

Taro has decided to build a tower by choosing some of the ~N~ blocks and stacking them vertically in some order. Here, the tower must satisfy the following condition:

• For each Block ~i~ contained in the tower, the sum of the weights of the blocks stacked above it is not greater than ~s_i~.

Find the maximum possible sum of the values of the blocks contained in the tower.

Constraints

• All values in input are integers.
• ~1 \le N \le 10^3~
• ~1 \le w_i, s_i \le 10^4~
• ~1 \le v_i \le 10^9~

Input Specification

The first line will contain the integer ~N~.

The next ~N~ lines will each contain three integers, ~w_i, s_i, v_i~.

Output Specification

Print the maximum possible sum of the values of the blocks contained in the tower.

Sample Input 1

3
2 2 20
2 1 30
3 1 40

Sample Output 1

50

Explanation For Sample 1

If Blocks ~2, 1~ are stacked in this order from top to bottom, this tower will satisfy the condition, with the total value of ~30+20=50~.

Sample Input 2

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

Sample Output 2

40

Explanation For Sample 2

Blocks ~1, 2, 3, 4~ should be stacked in this order from top to bottom.

Sample Input 3

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

Sample Output 3

5000000000

Explanation For Sample 3

The answer may not fit into a 32-bit integer type.

Sample Input 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

Sample Output 4

22

Explanation For Sample 4

We should, for example, stack Blocks ~5, 6, 8, 4~ in this order from top to bottom.