問題
太郎君は夏休み暇だったので探検することにしました。しばらくして、長い長い洞窟を発見しました。
洞窟の中はとても暗いのでこの先を探検するには明かりがほしいです。
洞窟の中には誰がつけたのか、いくつかのランタンがくくりつけられていました。
洞窟内にくくりつけられているランタンの数は全部でN個です。
i番目のランタンは入り口からliメートルの地点からriメートルの地点までを照らすことができます。
また、それぞれのランタンをつけるにはお金を払わなければならない仕組みになっているようです。
i番目のランタンをつけるにはCi円の費用がかかるようです。
すべてのランタンをつければ洞窟全体を照らすことは可能なようですが、
太郎君の持っているお小遣いはわずかであるため、可能な限り少ない費用で洞窟全体を照らしたいです。
入り口から洞窟の置くまではLメートルあるようです。
洞窟全体、つまり入り口の0メートル地点からLメートル地点までの全体を、少なくとも１つ以上のランタンで照らされているようにランタンをつけるとき、必要な費用の最小値を求めてください。
入力
N L l1 r1 c1 l2 r2 c2 : lN rN cN
1 行目にはランタンの個数を表す整数Nと洞窟の長さを表すを表す整数Lが空白区切りで与えられる。
2 行目からの N 行のうち i 行目にはi番目のランタンの照らす範囲を表す整数 li,riと、点けるのにかかる費用 ciが空白区切りで与えられる。
全てのランタンを点ければ、洞窟全体を照らすことができることが保証されている。
出力
洞窟全体を照らすのに必要な費用の最小値を1行で出力せよ。
制約
全ての入出力ケースについて以下を満たす。
- 1 ≦ N ≦ 105
- 1 ≦ L ≦ 105
- 0 ≦ li < ri ≦ L
- 1 ≦ ci ≦ 105
入出力例
入力例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