P10701 [SNCPC2024] 致命公司

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$。

无

无

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$。