Cake orders P58661


Statement
 

pdf   zip

thehtml
Ewelina loves baking beautiful cakes for special occasions. As a result of the quality of her work, she has received from friends and family more cake orders than she can handle, and she needs help to decide which orders to accept.

Ewelina has a list of n cake orders, each described by three integers: the delivery time Di, the amount of time Wi it will take her to complete the work, and the beauty Bi of the cake she has in mind. She would like to accept the subset of cake orders that maximizes the total sum of cake beauty, taking into account that she will never work on more than one cake at once, and that she will always work on a cake as late as possible (that is, between instant Di − Wi and instant Di) so that the cake is in the best condition when delivered.

Input

Input consists of several cases, each one with an n between 1 and 105, followed by n triples of integers Di Wi Bi. Assume 1 ≤ Wi ≤ Di ≤ 108 and 1 ≤ Bi ≤ 104.

Output

For every case, print the maximum possible sum of beauty of the delivered cakes.

Public test cases

  • Input

    2
10 4 1000
16 6 2000

2
10 4 1000
16 7 2000

5
900000 800000 5000
500000 100000 2000
900000 300000 2000
800000 350000 3000
300000 300000 2000

    Output

    3000
2000
6000
    • Information
    Author
    Félix Miravé
    Language
    English
    Official solutions
    C++
    User solutions
    C++