No.844 split game

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 89
作問者 : sinsincoscossinsincoscos / テスター : tempura_pptempura_pp
7 ProblemId : 2810 / 出題時の順位表

問題文

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行に出力してください。 最後に改行してください。

サンプル

サンプル1
入力
5 2 1
1 3 2
2 5 10
出力
9

マス1とマス2の間に黒線を引くと1点を失いますが,区間$[2,5]$ができて10点が得られるので,計9点となります。これが最適です。

サンプル2
入力
5 2 1
1 1 2
2 5 10
出力
11

マス1とマス2の間に黒線を引くと1点を失いますが,区間$[1,1]$と$[2,5]$ができて12点が得られるので,計11点となります。これが最適です。

サンプル3
入力
5 2 100
1 3 5
2 4 10
出力
0

黒線を引くコストが大きすぎるので,何もしないことが最適です。

サンプル4
入力
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

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。