問題文

umgくんは$1\times 1$のマスが横に$N$個並んだマス目を使ったゲームを遊ぶことにしました。左から$i$番目のマスをマス$i$と呼ぶことにします。 ゲームのルールは以下のようになっています。
・$1\le i \le N-1$をみたす整数$i$を$1$つ選んでマス$i$とマス$i+1$の間に黒い線を引く。$1$本引くごとに，umgくんは$A$点を失う。この操作を好きな回数繰り返す。つまり，黒線は何本引いてもよいし，$1$本も引かなくてもよい。
・$M$個の区間$[l_j,r_j] \ (1\le j \le M)$が与えられる。区間$[l_j,r_j]$が存在するとき，umgくんは$p_j$点を得る。ただし，区間$[l_j,r_j]$が存在するとは，以下の2つの条件を満たすことを言う。
　1. マス$l_j-1$とマス$l_j$の間，マス$r_j$とマス$r_j+1$の間にそれぞれ黒線が存在する。ただし，マス目$1$の左側と，マス目$N$の右側には最初から黒線が引いてあると考えてよい。
　2. マス$l_j$からマス$r_j$の間に黒線は$1$本もない。より正確に言えば，$l_j \le i \lt r_j$をみたすすべての整数$i$について，マス$i$とマス$i+1$の間に黒線はない。
umgくんが適切に黒線を引いたときに得られる得点の最大値を求めてください。

入力

$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$
$i\neq j$のとき，$(l_i,r_i)\neq (l_j,r_j)$
$1 \le p_j \le 10^9$

出力

答えを表す数値を1行に出力してください。 最後に改行してください。

サンプル

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