Surf

Interview

Time limit4sMemory limit256 MB

Summary

Pick waves with no wait-time overlap so the sum of fun points is as large as possible.

Level: Medium5 of 10
Topics: Dynamic programming, Sorting, Binary search
Solved: No attempts yet

Problem

You have taken up surfing in Florida, and you have the full schedule of today's waves. For each wave you know the minute it arrives, the fun points you earn by riding it, and how long you have to wait afterwards before you can ride again. The wait covers the ride itself plus the paddle back out to where the waves break.

If you ride the wave that arrives at minute $m_i$ , the next wave you ride has to arrive at minute $m_i + w_i$ or later. Anything that arrives earlier is gone before you are back in position.

Taking the wave with the most fun points is not always best. Consider these four waves:

Minute	Fun points	Wait time
2	80	9
8	50	2
10	40	2
13	20	5

Riding the waves at minutes 8, 10 and 13 earns 110 fun points. Riding the wave at minute 2 keeps you out of position until minute 11, so the only wave left is the one at minute 13, for a total of 100 fun points. The best total here is 110.

Given the complete list of waves for the day, find the largest total of fun points you can earn.

Input

The first line contains one integer $n$ ( $1 \le n \le 300\,000$ ), the number of waves for the day.

Each of the next $n$ lines contains three space separated integers $m_i$ , $f_i$ and $w_i$ ( $1 \le m_i, f_i, w_i \le 10^6$ ): the minute the $i$ -th wave arrives, its fun points, and its wait time.

No two waves arrive at the same minute. The waves are not necessarily listed in chronological order.

Output

Print one integer on a single line, the maximum total of fun points you can earn.

Examples2

Example 1
Input
```
4
8 50 2
10 40 2
2 80 9
13 20 5
```
Expected output
```
110
```

Example 2

Input

10
2079 809484 180
8347 336421 2509
3732 560423 483
2619 958859 712
7659 699612 3960
7856 831372 3673
5333 170775 1393
2133 989250 2036
2731 875483 10
7850 669453 842

Expected output