Problem D
Walkways

The Swedish team for the International Olympiad in Informatics has just landed in Singapore to compete in IOI 2020. On the way to the baggage claim, they have to pass through a long corridor with several moving walkways. The corridor is $M$ meters long, and the team is currently at the beginning of it, trying to figure out how quickly they can reach the baggage claim. There are $N$ moving walkways in the corridor. Each walkway starts at a certain distance from the beginning of the corridor, ends at a certain distance from the beginning of the corridor, and takes a certain amount of time to travel along. All walkways move in the direction of the corridor, and one can only step onto a walkway at the beginning of it and step off at the end of it. When the team is not on any walkway, it takes $g$ seconds to walk one meter. The corridor and walkways are narrow enough that only the time it takes to travel parallel to the corridor matters. Therefore, if one walkway ends at the same distance from the beginning as another walkway starts, it takes no time to move between the walkways. If the team plan their route optimally, how fast can they reach the end of the corridor?

Note that it may be advantageous to sometimes walk backward through the corridor to reach a walkway that takes one further ahead. However, there are no walkways going backward through the corridor.

Input

The first line of input contains three integers $N, M$ and $g$ ($1 \le N \le 2 \cdot 10^5$, $2 \le M \le 2 \cdot 10^5$, $1 \le g \le 100$), the number of walkways, the length of the corridor in meters and the speed of the team in seconds per meter.

The following $N$ lines each contain three integers describing a walkway, $s_ i, e_ i$ and $t_ i$ ($1\leq s_ i < e_ i\leq M,1\leq t_ i\leq 100$), the number of meters from the start of the corridor to the start of the walkway, the number of meters from the start of the corridor to the end of the walkway and how long it takes to use the walkway.

Output

Print an integer: how long it will take for the team to reach the end of the corridor if they plan their route optimally.

Points

Your solution will be tested on several test case groups. To get the points for a group, it must pass all the test cases in the group.

Explanation of Samples

Figure 1: Sample 1

In sample 1, it takes 2 seconds to walk one meter when the team is not on a walkway. The fastest way to reach the end is to walk to the walkway that takes 5 seconds, use it, then walk to the walkway that takes 2 seconds and use it. In total, this takes $4+5+2+2=13$ seconds.

Figure 2: Sample 2

In sample 2, it instead takes 5 seconds to walk one meter when the team is not on a walkway. The fastest way to reach the end is to walk to the walkway that takes 8 seconds, use it, and then go back one meter to use the walkway that takes 2 seconds, and then walk the final meter. In total, this takes $5+8+5+2+5=25$ seconds.

4 9 2
2 5 5
1 7 8
4 7 4
6 9 2

13

4 9 5
1 6 8
6 9 13
1 3 5
5 8 2

25