Milking Schedule

Bessie can produce milk during the next \(N\) hours. We label these hours as \(1, 2, \dots, N\). Farmer John (FJ) has \(M\) milking intervals available. The \(i\)-th interval starts at hour \(Start_i\) and ends at hour \(End_i\), in which FJ can get \(Eff_i\) gallons of milk.

After each milking session, Bessie must rest for \(R\) hours before FJ can begin the next session. Compute the maximum amount of milk Bessie can produce within the \(N\) hours if FJ optimally chooses some intervals.

inputFormat

The first line contains three integers \(N\), \(M\), and \(R\) (the total number of hours, the number of available milking intervals, and the resting time in hours, respectively).

Each of the following \(M\) lines contains three integers: \(Start_i\), \(End_i\), and \(Eff_i\), representing the start time, end time, and the amount of milk in gallons obtained during that interval.

outputFormat

Output a single integer which is the maximum amount of milk that can be produced within the \(N\) hours.

sample

10 3 1
1 3 5
4 6 6
7 10 5

16