시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 256 MB 23 12 12 75.000%

문제

Now that you’ve come to Florida and taken up surfing, you love it! Of course, you’ve realized that if you take a particular wave, even if it’s very fun, you may miss another wave that’s just about to come that’s even more fun. Luckily, you’ve gotten excellent data for each wave that is going to come: you’ll know exactly when it will come, how many fun points you’ll earn if you take it, and how much time you’ll have to wait before taking another wave. (The wait is due to the fact that the wave itself takes some time to ride and then you have to paddle back out to where the waves are crashing.) Obviously, given a list of waves, your goal will be to maximize the amount of fun you could have.

Consider, for example, the following list of waves:

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

In this example, you could take the waves at times 8, 10 and 13 for a total of 110 fun points. If you take the wave at time 2, you can’t ride another wave until time 11, at which point only 20 fun points are left for the wave at time 13, leaving you with a total of 100 fun points. Thus, for this input, the correct answer (maximal number of fun points) is 110.

Given a complete listing of waves for the day, determine the maximum number of fun points you could earn.

입력

The first line of input contains a single integer n (1 ≤ n ≤ 300,000), representing the total number of waves for the day. The ith line (1 ≤ i ≤ n) that follows will contain three space separated integers: mi, fi, and wi, (1 ≤ mi, fi, wi ≤ 106), representing the time, fun points, and wait time of the ith wave, respectively. You can ride another wave occurring at exactly time mi + wi after taking the ith wave. It is guaranteed that no two waves occur at the same time. The waves may not be listed in chronological order.

출력

Print, on a single line, a single integer indicating the maximum amount of fun points you can get riding waves.

예제 입력

4
8 50 2
10 40 2
2 80 9
13 20 5

예제 출력

110

예제 입력 2

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

예제 출력 2

3330913

힌트