Problem Description

There is a gate of width $ W $. Hereafter, we consider this gate as a line segment, and any point on this line segment has coordinates between $ 0 $ and $ W $ inclusive.

There are $ N $ stones fallen on this gate. The $ i $-th stone $(1 \leq i \leq N)$ occupies the interval $ (l_i, r_i) $ and costs $ p_i $ yen to remove. It is possible that the same location is occupied by multiple stones.

To allow cars to pass through, you want to remove some stones so that there exists a length $ C $ interval on this gate without any stones. Write a program to find the minimum amount of money needed to achieve this goal.

Input Format

The input is given from the 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 Format

Output an integer representing the minimum amount of money needed to achieve the goal. (Output 0 if no stones need to be removed.)

Sample Input and Output

Sample Input #1

3 10 5
1 3 100
8 10 123
4 6 3

Sample Output #1

3

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

Notes/Hints

Constraints

• $1 \leq N \leq 100,000$
• $10 \leq W \leq 1,000,000,000$
• $1 \leq C \leq W$
• $0 \leq l_i < r_i \leq W$
• $1 \leq p_i \leq 1,000,000,000$
• All values in the input are integers.

Sample Explanation 1

By paying $ 3 $ yen to remove the 3rd stone, a length $ 5 $ interval $ [3, 8] $ without any stones is created. This is the optimal choice.

Sample Explanation 2

The required amount of money can exceed the range of a 32-bit integer.

见题面 Input 部分

见题面 Output 部分