K. Lethal Company
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Recently, Shirost has been addicted to a game called Lethal Company.

In the game, players will act as contract workers for the company, collecting valuable waste from abandoned industrial planets. In the process of exploration, Shirost will encounter a monster called Coil-Head, which will move extremely rapidly when nobody is watching it, but will remain stationary when someone is watching it. As soon as approached by Coil-Head, workers will be killed immediately .

Now Shirost is standing at the intersection of $$$n$$$ infinitely long passages. He knows there will be $$$m$$$ Coil-Heads, appearing in the $$$x_i$$$ th passage at the $$$t_i$$$ th moment, $$$y_i$$$ meters away from him.

For each moment $$$j$$$, the following three events will occur in order:

  1. When the moment start, the Coil-Heads that satisfy $$$t_i = j$$$ will appear in the $$$x_i$$$-th passage, $$$y_i$$$ meters away from Shirost.
  2. Shirost chooses to watch exactly one passage.
  3. The Coil-Heads in this passage will be unable to move, but Coil-Heads which have appeared in other passages will move $$$k$$$ meters towards him. If any Coil-Head arrives at his position, he will die at the $$$j$$$ th moment.

Shirost wants to know the latest moment that he is alive. In other word, If Shirost is dead at the latest at the $$$j$$$ th moment, then you should output $$$j-1$$$. If he won't die, please output $$$-1$$$.

Input

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 passages, the number of Coil-Heads, the distance that the Coil-Heads moves at each moment.

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, representing the moment, the passage and the distance from Shirost when Coil-Head appears.

Output

Output a single integer on a single line, representing the latest moment of Shirost that he is alive. If he won't die, please output $$$-1$$$.

Examples
Input
2 3 2
1 1 6
2 2 7
3 1 8
Output
6
Input
114514 6 1919810
1 1 1
1 1 9
1 4 1
1 5 9
1 1 8
1 4 10
Output
0
Note

Shirost can act as follows:

momentpassage watched$$$1$$$st Coil-Head distance$$$2$$$nd Coil-Head distance$$$3$$$rd Coil-Head distance
116
2165
32456
41436
52234
61214

At the $$$7$$$ th moment, no matter which passage Shirost watches, he will be killed by Coil-Head at this moment. So the answer is $$$6$$$.