Uolevi is working at a giant megacorporation warehouse. He stacks boxes so that they take up less area. There are n boxes numbered 1,2,\dots,n. The i-th box has weight w_i\ kg, can hold c_i\ kg above it and has height h_i. Find the height of the tallest possible tower Uolevi can construct.

Input

The first line contains a single integer n. The i-th of the next n lines contains three integers w_i, c_i and h_i.

Output

Print the maximum height of the tallest possible tower.

Constraints

• 1 \leq n \leq 2000
• 1 \leq w_i, c_i, h_i \leq 2000

Example 1

Input:

2
2 2 3
3 1 4

Output:

4

Example 2

Input:

5
1 4 6
5 5 1
2 4 2
1 3 9
5 2 3

Output:

18