N - Land Clearing

Contest Duration: 2019-12-14(Sat) 04:00 - 2019-12-14(Sat) 09:00 (local time) (300 minutes) Back to Home

N - Land Clearing Editorial

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 と出力せよ。)

入力例 1Copy

Copy

出力例 1Copy

Copy

$3$ 円を支払って $3$ 番目の石を撤去すると、長さ $5$ の区間 $[3, 8]$ に石が存在しなくなる。これが最適な選択である。

入力例 2Copy

Copy

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

出力例 2Copy

Copy

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 1Copy

Copy

Sample Output 1Copy

Copy

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 2Copy

Copy

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 2Copy

Copy

3805189325

The amount of money may not fit into a $32$ -bit integer type.