Problem Statement

umg has decided to play a game using a grid of $N$ cells of size $1\times 1$ arranged in a horizontal row. The $i$-th cell from the left is called cell $i$. The rules of the game are as follows.
・Choose $1$ integer $i$ satisfying $1\le i \le N-1$ and draw a black line between cell $i$ and cell $i+1$. For every $1$ line drawn, umg loses $A$ points. This operation may be repeated any number of times. That is, any number of black lines may be drawn, and it is also allowed not to draw even $1$ line.
・$M$ intervals $[l_j,r_j] \ (1\le j \le M)$ are given. If the interval $[l_j,r_j]$ exists, umg gains $p_j$ points. Here, the interval $[l_j,r_j]$ is said to exist if the following 2 conditions are satisfied.
　1. There is a black line between cell $l_j-1$ and cell $l_j$, and there is a black line between cell $r_j$ and cell $r_j+1$. Here, you may consider that black lines are drawn from the beginning on the left side of cell $1$ and on the right side of cell $N$.
　2. There is not even $1$ black line between cell $l_j$ and cell $r_j$. More precisely, for every integer $i$ satisfying $l_j \le i \lt r_j$, there is no black line between cell $i$ and cell $i+1$.
Find the maximum score umg can obtain by drawing black lines appropriately.

Input

$N\ M\ A$
$l_1 \ r_1 \ p_1$
$l_2 \ r_2 \ p_2$
$\vdots$
$l_M \ r_M \ p_M$

$2 \le N \le 10^5$
$1 \le M \le \min(10^5, \frac{N(N+1)}{2})$
$1 \le A \le 10^9$
$1 \le l_j \le r_j \le N$
If $i\neq j$, then $(l_i,r_i)\neq (l_j,r_j)$
$1 \le p_j \le 10^9$

Output

Output the number representing the answer on 1 line. Print a newline at the end.

Sample

5 2 1
1 3 2
2 5 10

9

5 2 1
1 1 2
2 5 10

11

5 2 100
1 3 5
2 4 10

0

6 9 310889455
1 3 811332240
4 5 729061888
1 5 837866464
1 1 71272252
2 3 175965136
3 6 324033005
2 5 922077575
3 4 396994878
2 4 897759396

918615218