AT_past201912_n 整地

[problemUrl]: https://atcoder.jp/contests/past201912-open/tasks/past201912_n 幅 $ W $ の門がある。以下、この門を線分とみなし、線分上の任意の点は $ 0 $ 以上 $ W $ 以下の座標をもつとする。 この門の上に $ N $ 個の石が落ちている。$ i $ 個目の石 $ (1\ \leqq\ i\ \leqq\ N) $ は区間 $ (l_i,\ r_i) $ を占有し、撤去するのに必要な金額は $ p_i $ 円である。同じ地点が複数の石によって占有されている可能性もある。 車が通れるように、あなたは何個か石を取り除き、この門の上に石が存在しない長さ $ C $ の区間が存在するようにしたい。この目的を達成するために必要な最小の金額を求めるプログラムを作成せよ。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ W $ $ C $ $ l_1 $ $ r_1 $ $ p_1 $ $ l_2 $ $ r_2 $ $ p_2 $ $ : $ $ l_N $ $ r_N $ $ p_N $

目標の達成に必要な最小金額を表す整数を出力せよ。(石を取り除く必要がないときは `0` と出力せよ。)

### 注意 この問題に対する言及は、2019年12月29日 05:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - $ 1\ \leqq\ N\ \leqq\ 100,000 $ - $ 10\ \leqq\ W\ \leqq\ 1,000,000,000 $ - $ 1\ \leqq\ C\ \leqq\ W $ - $ 0\ \leqq\ l_i\