Cake orders P58661

0.65 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 $D_i$, the amount of time $W_i$ it will take her to complete the work, and the beauty $B_i$ 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 $D_i - W_i$ and instant $D_i$) so that the cake is in the best condition when delivered.

0.33

Input

Input consists of several cases, each one with an $n$ between 1 and $10^5$, followed by $n$ triples of integers $D_i$ $W_i$ $B_i$. Assume $1 \le W_i \le D_i \le 10^8$ and $1 \le B_i \le 10^4$.

Output

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