Path#5279
Nastia is walking from the cafeteria to the academic building, sending SMS messages to her friends in distant cities along the way. She receives replies frequently enough that she must send another SMS at least every -th step. Along her path, there are sunny areas that increase her temperature by a certain number of degrees at each stop, as well as sprinklers that decrease it.
Given the hot weather, Nastia aims to minimize her temperature by the time she reaches her destination. She wants to get there as quickly as possible, so she only moves forward towards the building.
The first line contains three integers (1 \leq n \leq 1000), (1 \leq k \leq x), and (0 \leq x \leq 1000) — the number of objects (sunny areas and sprinklers), the maximum number of steps between stops, and the length of Nastia's path in steps. Each of the following lines contains three integers: l_i, r_i (1 \leq l_i, r_i \leq x), and d_i (-10000 \leq d_i \leq 10000) — the coordinates of the segment corresponding to the -th object and the change in Nastia's temperature observed when stopping on this segment. It is guaranteed that no two segments overlap.
Output a single integer: the minimal possible total change in temperature that Nastia can obtain by the end of her journey.
Example 1
Example 2
Example 3