C - 蛍光灯 解説 /

実行時間制限: 2 sec / メモリ制限: 256 MB

問題文

ある小学校には、すごく長い廊下があります。東西に伸びていて、西端から東端まで L メートルあります。 学校の方針で窓は一切ついていないので、蛍光灯で廊下を照らさなければいけません。

この廊下には N 個の蛍光灯がついています。 i 番目の蛍光灯は西端から l_i メートルの地点と r_i メートルの地点の間を照らすことができます。 また、蛍光灯によって点けるのに必要な費用が違います。 i 番目の蛍光灯を点けるには c_i 円の費用がかかります。

全ての蛍光灯を点ければ、廊下全体を照らすことは可能ですが、お金がないので可能な限り少ない費用で廊下全体を照らしたいです。 廊下のどの地点、つまり西端から 0 メートルの地点と L メートルの地点の間のどの地点も少なくとも1つ以上の蛍光灯に照らされているように蛍光灯を点けるとき、必要な費用の最小値を求めてください。

入力

入力は以下の形式で標準入力から与えられる。

N L
l_1 r_1 c_1
l_2 r_2 c_2
:
l_N r_N c_N

制約に不十分な記述があったため、修正しました。「蛍光灯の照らす範囲」→「蛍光灯の照らす範囲を表す整数」（21:20）

  • 1 行目には蛍光灯の個数を表す整数 N (1 ≦ N ≦ 10^5) と廊下の長さを表すを表す整数L(1 ≦ L ≦ 10^5)が空白区切りで与えられる。
  • 2 行目からの N 行のうち i 行目にはi番目の蛍光灯の照らす範囲を表す整数 l_i, r_i (0 ≦ l_i ＜ r_i ≦ L) と、点けるのにかかる費用 c_i (1 ≦ c_i ≦ 10^5) が空白区切りで与えられる。
  • 全ての蛍光灯を点ければ、廊下全体を照らすことができることが保証されている。

部分点

この問題には部分点が設定されている。

  • 1 ≦ N ≦ 3,000 ,1 ≦ L ≦ 3,000を満たすデータセットに正解した場合は 60 点が与えられる。
  • 1 ≦ N ≦ 10^5 ,1 ≦ L ≦ 10^5を満たすデータセットに正解した場合はさらに 40 点が与えられる。合計で100点となる。

出力

廊下全体を照らすのに必要な費用の最小値を1行で出力せよ。

入力例1

5 5
0 1 1
1 2 1
2 4 3
3 5 1
2 3 2

出力例1

5

1, 2, 4, 5番目の蛍光灯を点けた時、費用の総和が最小になります。

入力例2

8 10
0 2 1
2 3 1
0 4 1
0 2 1
3 7 1
0 10 1080
8 10 1
9 10 1

出力例2

1080

6番目の蛍光灯を点けない限り、西端から7メートルの地点と8メートルの地点の間は照らされません。 6番目の蛍光灯だけを使うのが、最適な点け方です。

入力例3

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

出力例3

6

入力例4

5 5
0 1 100000
1 2 100000
2 3 100000
3 4 100000
4 5 100000

出力例4

500000