题目背景

:::warning{open} This question uses the original question data, but there is a problem with the original question data relative to the question surface. The actual data for this question is $0 \le Start_i<end_i \le N$. :::

题目描述

Bessie can produce milk in the next $N$ hours. For convenience, we number these $N$ hours $0 \dots N - 1$.

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.

12 4 2
1 2 8
10 12 19
3 6 24
7 10 31

43

提示

Constraints

For all testdata, it is guaranteed that $1 \le N \le 10^6$, $1 \le M \le 10^3$, $0 \le Start_i < End_i \le N - 1$, and $1 \le Eff_i \le 10^6$.

Translated by ChatGPT 5