問題文

カズマ君は球感波(キュウカンバ)小学校の運動会に来ています. この運動会では N 個の競技が実施され, それぞれの競技には 0 から N - 1 の整数の番号が着いています.

i 番目の競技は時刻 A_i に始まって時刻 B_i に終わり, カズマ君はこの競技に参加すると F_i の楽しさを得ることができます.

球感波小学校の校庭は広いため, 複数の競技を同時に行うことができます. つまり, N 種類の競技のうち複数個の競技時間が重複することがあります.

カズマ君は開催時間が重なっている競技には参加出来ません. ただし, ある競技が終わった直後に始まる別の競技には参加できます. すなわち, 終了時間と開始時間が同じ競技に参加することは可能です.

カズマ君はできるだけ運動会を楽しみたいと思っていますが, 真夏の炎天下では長い時間運動会に参加するほど体力が消耗され, その分楽しさも減ってしまいます. 具体的には, 1 単位時間運動会に参加すると C だけカズマ君の楽しさは減少します. また, このとき競技に参加していなくても体力は減少し続けます.

カズマ君はインドア派なので, 効率的に運動会に参加して暑さを免れたいです. すなわち, カズマ君は好きな時刻から運動会に参加し始めても良いし, 好きな時間に帰っても良いです.

このとき, カズマ君が得られる楽しさの最大値を求めて下さい.

課題

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.

入力例 1

5 3
1 4 12
3 6 7
2 3 6
4 8 8
8 9 10

出力例 1

7

5 番目の区間を選ぶと, その集合のスコアは 7 となり, スコアの最大値を達成できる.

入力例 2

5 2
1 4 12
3 6 7
2 3 6
4 8 8
8 9 10

出力例 2

14