Problem Description

Shirost has recently become obsessed with a game called "Deadly Company."

In the game, players act as contract workers for a "company," collecting scrap from abandoned industrial planets. During the exploration, Shirost encounters a monster called the Springhead, which moves quickly when not being watched but remains stationary when observed. Once it gets close, it will immediately kill Shirost.

Now, Shirost stands at the intersection of $n$ infinitely long corridors. He knows there are $m$ Springheads that will appear at time $t_i$ in the $x_i$-th corridor at a distance of $y_i$ meters from him.

For each time $j$, the following three events will occur in sequence:

1. At the beginning of the time $j$, Springheads with $t_i = j$ will appear in the $x_i$-th corridor at a distance of $y_i$ meters from Shirost.

2. Shirost chooses to gaze at any one corridor.

3. All Springheads in the gazed corridor cannot move, while Springheads in other corridors that have already appeared will move $k$ meters towards him. If any Springhead reaches his position, he will die at time $j$.

Shirost wants to know the latest time he can survive. In other words, if Shirost dies at the latest at time $j$, you need to output $j-1$. If he will not die, output $-1$.

Input Format

The first line of input contains three integers $n, m, k$ ($1 \leq n \leq 5 \times 10^5, 1 \leq m \leq 5 \times 10^5, 1 \leq k \leq 10^{18}$), separated by spaces, representing the number of infinitely long corridors, the number of Springheads, and the distance each Springhead moves per time unit.

The next $m$ lines each contain three integers $t_i, x_i, y_i$ ($1 \leq t_i \leq 10^{18}, 1 \leq x_i \leq n, 1 \leq y_i \leq 10^{18}$), separated by spaces, describing the appearance time, corridor number, and distance from Shirost for each Springhead.

Output Format

Output a single integer on one line, representing the latest time Shirost can survive. If he will not die, output $-1$.

Sample Input and Output

Input Sample #1

2 3 2
1 1 6
2 2 7
3 1 8

Output Sample #1

6

Input Sample #2

114514 6 1919810
1 1 1
1 1 9
1 4 1
1 5 9
1 1 8
1 4 10

Output Sample #2

0

Notes

Shirost can act as follows:

At time 7, regardless of which corridor Shirost looks at, he will be killed by a Springhead within that time. Therefore, the answer is 6.

见题面 Input 部分

见题面 Output 部分