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