Protecting the mines

When playing video games, resource management is vital.

There are n gold mines at different locations . Each of those mines can produce a certain amount of gold . Yet, protecting those mines from enemies is very demanding and requires a lot of energy. Luckily, you can get energy from each gold mine as well. Each gold mine produces a certain amount of energy .

You would like to select a contiguous segment of gold mines and protect them, making sure you can earn as much gold as possible. When selecting a segment, you need to have energy at least the length of the segment to be able to protect it from enemies.

How much gold would be possible to obtain from the mines?

Input

The first line of the input contains a single integer n (1 ≤ n ≤ ).

The next n lines contain 3 space-separated integers (1 ≤ ≤ ) the coordinate of the gold mine, how much gold it can produce, and the amount of energy it produces. All the coordinates are guaranteed to be different and are given in increasing order.

Output

The program should print the maximum amount of gold possible to obtain from the gold mines safely.

Examples

Input	Output
4 1 5 1 2 7 2 5 4 1 8 15 1	16
2 1 4 1 4 5 1	5

Explanation

The first example → 16

X	1	2	3	4	5	6	7	8
Energy	1	2	ㅤ	ㅤ	1	ㅤ	ㅤ	1
Gold	5	7	ㅤ	ㅤ	4	ㅤ	ㅤ	15

You can take the first 3 mines ⇒ The segment length would be 5-1 = 4 (the mines are at the endpoints of coordinates), the energy produced by the mines would be 1+2+1 = 4, and the gold obtained would be 5+7+4 = 16.

The second example → 5

X	1	2	3	4
Energy	1	ㅤ	ㅤ	1
Gold	4	ㅤ	ㅤ	5

You can pick the last gold min ⇒ The segment length is 0, the energy produced by the mine is 1, and the gold obtained would be 5.

Hint 1

You might need to apply different techniques on the left and the right parts when performing a divide & conquer approach.

Hint 2

You can try to calculate the answers that pass through the midpoint

Input

Output

Examples

Explanation

Constraints

To check your solution you need to sign in

Sign in to continue