P2889 [USACO07NOV] Milking Time S

Bessie can produce milk in the next $N$ hours. For convenience, we number these $N$ hours $1 \dots N$. Within these $N$ hours, FJ has $M$ intervals during which he can milk Bessie. The $i$-th interval runs from $Start_i$ to $End_i$ and yields $Eff_i$ gallons of milk. After each milking, Bessie must rest for $R$ hours before FJ can start the next milking. Now, FJ needs you to compute the maximum total milk Bessie can produce within these $N$ hours.

The first line contains three integers, representing $N$, $M$, and $R$. Lines $2 \dots M+1$: the $(i+1)$-th line contains three integers $Start_i$, $End_i$, and $Eff_i$, describing one milking interval.

Output a single integer on one line: the answer.

#### Constraints For all testdata, it is guaranteed that $1 \le N \le 10^6$, $1 \le M \le 10^3$, $1 \le Start_i < End_i \le N$, and $1 \le Eff_i \le 10^6$. Translated by ChatGPT 5