B. Uchiage Hanabi
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

One forgotten night, KP was feeling down while staring at his computer. Seeing this, LW decided to cheer him up with something special.

LW brought KP to a straight road with $$$n$$$ points; point $$$i$$$ is at position $$$i$$$, respectively. At the beginning of each time, KP can choose a position to teleport. But he can only teleport no more than $$$d$$$ distance each time and does not exceed the boundary (i.e. if KP is at position $$$x$$$ at the end of time $$$i - 1$$$, then at the beginning of time $$$i$$$, he can teleport to any position in $$$[\max(1, x - d), \min(n, x + d)]$$$, even between two points). Specially, at the beginning of time $$$1$$$, KP can teleport to either point $$$1$$$ or point $$$n$$$.

Unlike usual, there will be $$$m$$$ fireworks shows taking place on some points tonight. At the end of time $$$t_i$$$, a fireworks show will happen at point $$$a_i$$$. If KP is currently at point $$$x$$$, then he will gain $$$b_i \cdot |x - a_i|$$$ happiness. Note that happiness may be negative.

Help LW calculate the maximum total happiness KP can gain after all the fireworks shows.

Input

The first line contains three integers $$$n, m, d$$$ $$$(1 \leq d \leq n \leq 10^5, 1 \leq m \leq 500)$$$, denoting the number of points on the road, the number of fireworks shows, and the maximum distance KP can move in each time unit.

For the following $$$m$$$ lines, the $$$i$$$-th line contains three integers $$$a_i, b_i, t_i$$$ $$$(1 \leq a_i \leq n, 1 \leq |b_i|, t_i \leq 10^9)$$$, denoting the parameters of a fireworks show as described.

It's guaranteed that $$$t_i$$$ is non-decreasing, i.e. $$$t_{i-1} \leq t_i$$$ is guaranteed for all $$$1 \lt i \leq m$$$.

Output

Output a line containing one integer, denoting the maximum total happiness KP can gain after all fireworks shows. It can be proved that the answer will always be an integer.

Examples
Input
100 1 5
1 50 1
Output
4950
Input
7 5 3
4 67 88
1 50 88
2 50 88
3 50 88
4 -50 89
Output
951
Note

For the first test case, KP can initially teleport to $$$1$$$ or $$$n$$$ at the beginning of time $$$1$$$. Since the only firework will happen at point $$$1$$$, he chooses to start with $$$n$$$ (i.e. $$$100$$$), and will gain $$$50 \times |100 - 1| = 4950$$$ happiness.