Cake orders

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

[image]

Input

Input consists of several cases, each one with an n between 1 and 10⁵,
followed by n triples of integers D_(i) W_(i) B_(i). Assume
1 ≤ W_(i) ≤ D_(i) ≤ 10⁸ and 1 ≤ B_(i) ≤ 10⁴.

Output

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

Problem information

Author: Félix Miravé

Generation: 2026-01-25T11:31:22.804Z

© Jutge.org, 2006–2026.
https://jutge.org
