Milking Time

Bessie is a very hard-working cow, and she wants to maximize how much milk she produces. She plans her next $N$ ($1 \le N \le 10^6$) hours, labeled $0 \dots N-1$, so that she produces as much milk as possible during them.

Farmer John has a list of $M$ ($1 \le M \le 1000$) possibly overlapping intervals during which he is available for milking. Interval $i$ has a starting hour $s_i$ ($0 \le s_i < N$), an ending hour $e_i$ ($s_i < e_i \le N$), and an efficiency $w_i$ ($1 \le w_i \le 10^6$), which is the number of gallons of milk Bessie produces during that interval. Milking starts at the beginning of the starting hour and stops at the beginning of the ending hour. If Bessie is milked during an interval, she must be milked through the entire interval.

After being milked during any interval, Bessie must rest $R$ ($1 \le R \le N$) hours before she can start milking again. That is, if she is milked during an interval that ends at hour $e$, the next interval she is milked in must start at hour $e + R$ or later. Given Farmer John's list of intervals, determine the maximum amount of milk Bessie can produce during the $N$ hours.

• Line 1: three space-separated integers $N$, $M$, and $R$.
• Lines 2 to $M+1$: line $i+1$ describes the $i$-th milking interval with three space-separated integers $s_i$, $e_i$, and $w_i$.

• Line 1: the maximum number of gallons of milk Bessie can produce during the $N$ hours.