AT_k4pc_d たのしい運動会(School Sports is Fun)

[problemUrl]: https://atcoder.jp/contests/k4pc/tasks/k4pc_d カズマ君は球感波(キュウカンバ)小学校の運動会に来ています. この運動会では $ N $ 個の競技が実施され, それぞれの競技には $ 0 $ から $ N\ -\ 1 $ の整数の番号が着いています. $ i $ 番目の競技は時刻 $ A_i $ に始まって時刻 $ B_i $ に終わり, カズマ君はこの競技に参加すると $ F_i $ の楽しさを得ることができます. 球感波小学校の校庭は広いため, 複数の競技を同時に行うことができます. つまり, $ N $ 種類の競技のうち複数個の競技時間が重複することがあります. カズマ君は開催時間が重なっている競技には参加出来ません. ただし, ある競技が終わった直後に始まる別の競技には参加できます. すなわち, 終了時間と開始時間が同じ競技に参加することは可能です. カズマ君はできるだけ運動会を楽しみたいと思っていますが, 真夏の炎天下では長い時間運動会に参加するほど体力が消耗され, その分楽しさも減ってしまいます. 具体的には, $ 1 $ 単位時間運動会に参加すると $ C $ だけカズマ君の楽しさは減少します. また, このとき競技に参加していなくても体力は減少し続けます. カズマ君はインドア派なので, 効率的に運動会に参加して暑さを免れたいです. すなわち, カズマ君は好きな時刻から運動会に参加し始めても良いし, 好きな時間に帰っても良いです. このとき, カズマ君が得られる楽しさの最大値を求めて下さい.

> $ N $ $ C $ $ A_1 $ $ B_1 $ $ F_1 $ : $ A_N $ $ B_N $ $ F_N $

問題の解を $ 1 $ 行に出力せよ．

### 課題 $ N $ 個の区間が整数列 $ A $, $ B $ によって与えられる．$ i $ 番目の区間は半開区間 $ [A_i,\ B_i) $ （$ A_i $ は含むが $ B_i $ は含まない）である．また，各区間には非負整数の重みがついており，$ i $ 番目の区間の重みは $ F_i $ である． 与えられた区間の中から, 互いに重なっていない $ 0 $ 個以上の区間を選ぶことを考え, 選ばれた区間の番号の集合を $ G $ としよう. このとき, $ L\ =\ min\ \{A_i\ |\ i\ \in\ G\ \} $, $ R\ =\ max\{B_i\ |\ i\ \in\ G\} $ としたときに, 非負整数の定数 $ C $ を用いた値 $ (Σ\ _{i\ \in\ G}\ F_i)\ -\ C\ \times\ (R\ -\ L) $ を $ G $ のスコアと呼ぶことにする. ただし $ G $ が空集合のときのスコアは $ 0 $ とする. うまく $ G $ の要素を選んだときのスコアを最大化せよ. ### 制約 すべての入力データは以下の制約を満たす． - $ 1\ ≦\ N\ ≦\ 10^5 $. - $ 0\ ≦\ C\ ≦\ 10^4 $. - $ 0\ ≦\ A_i\ ＜\ B_i\ ≦\ 10^5 $. - $ 0\ ≦\ F_i\ ≦\ 10^4 $. また，この問題には部分点が設定されており，$ 1 $ 点分の入力データは追加で以下の制約を満たす． - $ N\ ≦\ 1000 $. ### Sample Explanation 1 $ 5 $ 番目の区間を選ぶと, その集合のスコアは $ 7 $ となり, スコアの最大値を達成できる.