実行時間制限: 2 sec / メモリ制限: 256 MB
問題文
カズマ君は球感波(キュウカンバ)小学校の運動会に来ています. この運動会では 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.
入力
N C A_1 B_1 F_1 : A_N B_N F_N
出力
問題の解を 1 行に出力せよ.
入力例 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
Problem: ey429
Tester: kyuridenamida, kagamiz, japlj