{"problem":{"name":"[SNCPC2024] 致命公司","description":{"content":"Shirost 最近沉迷于一款名为《致命公司》的游戏。 在游戏中，玩家将作为“公司”的合同工，从废弃的工业星球收集废料。在探索的过程中，Shirost 将遇到一个名为弹簧头的怪物，弹簧头会在无人注视它时快速移动，但在被注视时则会保持不动。一旦接近，弹簧头就会立刻杀死 Shirost。 现在 Shirost 站在 $n$ 个无限长的通道的交汇点，他知道有 $m$ 个弹簧头，分别会在 $t_i$ ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10701"},"statements":[{"statement_type":"Markdown","content":"Shirost 最近沉迷于一款名为《致命公司》的游戏。\n\n在游戏中，玩家将作为“公司”的合同工，从废弃的工业星球收集废料。在探索的过程中，Shirost 将遇到一个名为弹簧头的怪物，弹簧头会在无人注视它时快速移动，但在被注视时则会保持不动。一旦接近，弹簧头就会立刻杀死 Shirost。\n\n现在 Shirost 站在 $n$ 个无限长的通道的交汇点，他知道有 $m$ 个弹簧头，分别会在 $t_i$ 时刻出现在 $x_i$ 号通道距离他 $y_i$ 米远处。\n\n对于每个时刻 $j$，以下三个事件将会依次发生：\n\n1. 在该时刻开始时，满足 $t_i = j$ 的弹簧头会出现在  $x_i$ 号通道距离 Shirost $y_i$ 米远处。\n\n2. Shirost 选择凝视任意一个通道。\n\n3. 该通道内的所有弹簧头无法移动，而其他通道中**已经出现**的弹簧头会向他移动 $k$ 米，如果某个弹簧头到达他所在位置，则他将在时刻 $j$ 死亡。\n\nShirost 想知道他最晚可以活到哪个时刻。换句话说，如果 Shirost 最晚在时刻 $j$ 死亡，那么你需要输出 $j-1$。如果他不会死亡，则输出 $-1$。\n\n## Input\n\n输入第一行为三个整数 $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}$)，由空格隔开，为无限长通道的个数，弹簧头的个数，弹簧头每时刻移动的距离。\n\n接下来 $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 有多远。\n\n## Output\n\n输出仅一行一个整数，表示 Shirost 最晚可以活到哪个时刻。如果他不会死亡，则输出 $-1$。\n\n[samples]\n\n## Note\n\nShirost 可以按如下所述行动：\n| 时刻 | 凝视的通道 | 弹簧头 $1$ 距离 | 弹簧头 $2$ 距离 |  弹簧头 $3$ 距离 |\n| :----------: | :----------: | :----------: | :----------: | :----------: |\n| 1 | 1 | 6 |  |  |\n| 2 | 1 | 6 | 5 |  |\n| 3 | 2 | 4 | 5 | 6 |\n| 4 | 1 | 4 | 3 | 6 |\n| 5 | 2 | 2 | 3 | 4 |\n| 6 | 1 | 2 | 1 | 4 |\n\n在第 $7$ 时刻，无论看哪个通道，Shirost 都会在该时刻内被弹簧头杀死。所以答案是 $6$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10701","tags":["2024","O2优化","陕西","省赛/邀请赛"],"sample_group":[["2 3 2\n1 1 6\n2 2 7\n3 1 8\n","6\n"],["114514 6 1919810\n1 1 1\n1 1 9\n1 4 1\n1 5 9\n1 1 8\n1 4 10\n","0\n"]],"created_at":"2026-03-03 11:09:25"}}