Description

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.

Input Format

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 Format

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

Hint

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