题目描述

Shirost 最近沉迷于一款名为《致命公司》的游戏。

在游戏中，玩家将作为“公司”的合同工，从废弃的工业星球收集废料。在探索的过程中，Shirost 将遇到一个名为弹簧头的怪物，弹簧头会在无人注视它时快速移动，但在被注视时则会保持不动。一旦接近，弹簧头就会立刻杀死 Shirost。

现在 Shirost 站在 $n$ 个无限长的通道的交汇点，他知道有 $m$ 个弹簧头，分别会在 $t_i$ 时刻出现在 $x_i$ 号通道距离他 $y_i$ 米远处。

对于每个时刻 $j$，以下三个事件将会依次发生：

1. 在该时刻开始时，满足 $t_i = j$ 的弹簧头会出现在 $x_i$ 号通道距离 Shirost $y_i$ 米远处。

2. Shirost 选择凝视任意一个通道。

3. 该通道内的所有弹簧头无法移动，而其他通道中已经出现的弹簧头会向他移动 $k$ 米，如果某个弹簧头到达他所在位置，则他将在时刻 $j$ 死亡。

Shirost 想知道他最晚可以活到哪个时刻。换句话说，如果 Shirost 最晚在时刻 $j$ 死亡，那么你需要输出 $j-1$。如果他不会死亡，则输出 $-1$。

输入格式

输入第一行为三个整数 $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}$)，由空格隔开，为无限长通道的个数，弹簧头的个数，弹簧头每时刻移动的距离。

接下来 $m$ 行，每行三个整数 $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}$)，由空格隔开，描述弹簧头出现的时刻，出现的通道编号，距离 Shirost 有多远。

输出格式

输出仅一行一个整数，表示 Shirost 最晚可以活到哪个时刻。如果他不会死亡，则输出 $-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

提示

Shirost 可以按如下所述行动： | 时刻 | 凝视的通道 | 弹簧头 $1$ 距离 | 弹簧头 $2$ 距离 | 弹簧头 $3$ 距离 | | :----------: | :----------: | :----------: | :----------: | :----------: | | 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 |

在第 $7$ 时刻，无论看哪个通道，Shirost 都会在该时刻内被弹簧头杀死。所以答案是 $6$。