[ARC026C] 蛍光灯

##### 题目描述 有一所小学，走廊贼长，为东西走向，长度为L。由于这个走廊木有窗户，所以学校希望能够照亮走廊，防止小盆友摔倒。现在我们有n个荧光灯可供选择，第i个荧光灯可以从li照到ri。并且每一个荧光灯都有自己的价格。Ci表示其价格。如果把所有荧光灯点亮，那么这个走廊一定能被照亮。但是我们并没有这么多钱。这条走廊从0开始到L结束。我们需要求在照亮走廊的每一个位置的前提下，求出最小价格。 ##### 输入输出格式 第一行输入两个数 N (1 ≦ N ≦ 100000)和L (1 ≦ L ≦ 100000) 用空格隔开。 接下来的n行分别输入每个灯能照亮的区间（从l到r）和这盏灯的价格用空格隔开。 保证一定有解。 最小值为1。 ###### Sample Explanation 1 当我们点亮编号1,2,4,5编号的荧光灯时，费用最少 ###### Sample Explanation 2 因为点亮一个6号荧光灯就相当于点亮1,2,3,4,5号荧光灯，且价格更少。 故选6号是最合适的。

[problemUrl]: https://atcoder.jp/contests/arc026/tasks/arc026_3 ある小学校には、すごく長い廊下があります。東西に伸びていて、西端から東端まで $ 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行で出力せよ。

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

5

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

1080

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

6

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

500000

### 部分点 この問題には部分点が設定されている。 - $ 1\ ≦\ N\ ≦\ 3,000\ ,1\ ≦\ L\ ≦\ 3,000 $を満たすデータセットに正解した場合は $ 60 $ 点が与えられる。 - $ 1\ ≦\ N\ ≦\ 10^5\ ,1\ ≦\ L\ ≦\ 10^5 $を満たすデータセットに正解した場合はさらに $ 40 $ 点が与えられる。合計で$ 100 $点となる。 ### Sample Explanation 1 $ 1,\ 2,\ 4,\ 5 $番目の蛍光灯を点けた時、費用の総和が最小になります。 ### Sample Explanation 2 $ 6 $番目の蛍光灯を点けない限り、西端から$ 7 $メートルの地点と$ 8 $メートルの地点の間は照らされません。 $ 6 $番目の蛍光灯だけを使うのが、最適な点け方です。