/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
注意
この問題に対する言及は、2019年12月29日 05:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。
試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。
問題文
幅 W の門がある。以下、この門を線分とみなし、線分上の任意の点は 0 以上 W 以下の座標をもつとする。
この門の上に N 個の石が落ちている。i 個目の石 (1 \leqq i \leqq N) は区間 (l_i, r_i) を占有し、撤去するのに必要な金額は p_i 円である。同じ地点が複数の石によって占有されている可能性もある。
車が通れるように、あなたは何個か石を取り除き、この門の上に石が存在しない長さ C の区間が存在するようにしたい。この目的を達成するために必要な最小の金額を求めるプログラムを作成せよ。
制約
- 1 \leqq N \leqq 100,000
- 10 \leqq W \leqq 1,000,000,000
- 1 \leqq C \leqq W
- 0 \leqq l_i < r_i \leqq W
- 1 \leqq p_i \leqq 1,000,000,000
- 入力中の値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N W C l_1 r_1 p_1 l_2 r_2 p_2 : l_N r_N p_N
出力
目標の達成に必要な最小金額を表す整数を出力せよ。(石を取り除く必要がないときは 0 と出力せよ。)
入力例 1
3 10 5 1 3 100 8 10 123 4 6 3
出力例 1
3
3 円を支払って 3 番目の石を撤去すると、長さ 5 の区間 [3, 8] に石が存在しなくなる。これが最適な選択である。
入力例 2
22 30 10 0 30 1000000000 0 30 1000000000 0 30 1000000000 7 30 261806 6 19 1 5 18 1238738 12 28 84 10 14 5093 9 20 9 15 26 8739840 6 8 240568 14 19 198 2 4 1102 1 29 5953283 9 20 183233 9 13 44580 6 23 787237159 12 14 49 28 29 9020727 14 20 318783 2 19 9862194 9 30 166652
出力例 2
3805189325
必要な金額が 32 bit 整数型に収まらないことがある。
Warning
Do not make any mention of this problem until December 29, 2019, 05:00 a.m. JST. In case of violation, compensation may be demanded.
After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).
Problem Statement
There is a gate of width W. Below, we will regard this gate as a segment, and assume that a point on this segment has a coordinate between 0 and W (inclusive).
We have N stones scattered on the gate. The i-th stone (1 \leq i \leq N) occupies the segment (l_i, r_i), and it costs p_i yen (the currency of Japan) to remove it. Multiple stones may occupy the same point.
You want to allow a car to pass through this gate by removing some stones so that there will be a segment of length C not overlapping with a stone. Write a program to find the minimum amount of money to do so.
Constraints
- 1 \leq N \leq 100000
- 10 \leq W \leq 10^9
- 1 \leq C \leq W
- 0 \leq l_i < r_i \leq W
- 1 \leq p_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N W C l_1 r_1 p_1 l_2 r_2 p_2 : l_N r_N p_N
Output
Print the integer representing the minimum amount of money needed to achieve the objective (or print 0 if no stone needs to be removed).
Sample Input 1
3 10 5 1 3 100 8 10 123 4 6 3
Sample Output 1
3
If we remove the third stone for 3 yen, no stone will overlap the segment [3, 8] of length 5. This is the optimal choice.
Sample Input 2
22 30 10 0 30 1000000000 0 30 1000000000 0 30 1000000000 7 30 261806 6 19 1 5 18 1238738 12 28 84 10 14 5093 9 20 9 15 26 8739840 6 8 240568 14 19 198 2 4 1102 1 29 5953283 9 20 183233 9 13 44580 6 23 787237159 12 14 49 28 29 9020727 14 20 318783 2 19 9862194 9 30 166652
Sample Output 2
3805189325
The amount of money may not fit into a 32-bit integer type.