Problem Description

Shirost has recently been addicted to a game called Lethal Company.

In the game, players act as contractors of the “Company” and collect scrap from abandoned industrial planets. During exploration, Shirost will encounter a monster called a “Springhead”. A Springhead moves quickly when nobody is watching it, but stays still when it is being watched. Once it gets close, the Springhead will kill Shirost immediately.

Now Shirost is standing at the intersection of $n$ infinitely long corridors. He knows that there are $m$ Springheads: the $i$-th Springhead will appear at time $t_i$, in corridor $x_i$, at a position $y_i$ meters away from him.

For each time $j$, the following three events happen in order:

1. At the beginning of this time, every Springhead with $t_i = j$ appears in corridor $x_i$, at a position $y_i$ meters away from Shirost.

2. Shirost chooses to stare at any one corridor.

3. All Springheads in that corridor cannot move, while Springheads that have already appeared in other corridors move $k$ meters toward him. If any Springhead reaches Shirost’s position, then he will die at time $j$.

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

Input Format

The first line 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 a Springhead moves each 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 time when a Springhead appears, the corridor index where it appears, and how far it is from Shirost.

Output Format

Output one integer in a single line, indicating the latest time Shirost can stay alive. If he will never die, output $-1$.

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

6

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

0

Hint

Shirost can act as follows: | Time | Corridor stared at | Springhead $1$ distance | Springhead $2$ distance | Springhead $3$ distance | | :----------: | :----------: | :----------: | :----------: | :----------: | | 1 | 1 | 6 | | | | 2 | 1 | 6 | 5 | | | 3 | 2 | 4 | 5 | 6 | | 4 | 1 | 4 | 3 | 6 | | 5 | 2 | 2 | 3 | 4 | | 6 | 1 | 2 | 1 | 4 |

At time $7$, no matter which corridor he stares at, Shirost will be killed by a Springhead during this time. Therefore, the answer is $6$.

Translated by ChatGPT 5