408565: GYM103186 H 鸡哥的 AI 驾驶

Memory Limit:1024 MB Time Limit:4 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

H. 鸡哥的 AI 驾驶time limit per test4 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

鸡哥最近正在制作一款游戏《狭道赛车手X》,他为游戏中的车辆编写了一个自动驾驶AI,使得游戏中的车辆的车辆能够在将要撞到别的车辆时自动绕过对方,且不需要减速。

然而游戏上线后鸡哥突然发现代码中存在一个 bug,会让不同型号的车辆相遇时发生事故(追尾或者相撞)!

鸡哥希望能在玩家发现这个 bug 前推出一个《1.22热修复补丁》,否则游戏的评分就会非常难看。在他开始编写代码前,鸡哥想要知道玩家还要多久才能发现这个 bug。一旦有事故发生,玩家就会立刻发现这个 bug。

鸡哥将每一辆车看做一条直线上的点,每辆车以(位置,速度,型号)这样的三元组给出。当型号相同的两辆车位于同一坐标时,不会发生事故,但不同型号的两辆车位于同一坐标时,就会发生车祸。

鸡哥觉得这个任务非常简单,于是他将这个任务交给了你,为了给鸡哥一些时间来推送这个补丁,你需要告诉鸡哥的时间是 $$$t$$$:满足在 $$$[0,t]$$$ 时间内没有发生事故,在 $$$(t,t+1]$$$ 的时间内发生了某起(或多起)事故。

Input

第一行有两个整数 $$$n,k$$$ ($$$1 \le k \le n \le 10^5)$$$,分别表示车辆的数量和不同型号的种数。

接下来的 $$$n$$$ 行,第 $$$i$$$ 行有三个整数 $$$p_i,v_i,t_i$$$ ($$$-10^9 \le p_i,v_i \le 10^9,1 \le t_i \le k$$$),分别表示第 $$$i$$$ 辆车的位置、速度和型号。

输入保证任意两辆车初始时不会在同一位置。

Output

在一行输出一个整数,表示你需要告诉鸡哥的时间 $$$t$$$。

特别地,如果永远不会有事故发生,输出 $$$-1$$$。

ExamplesInput
5 2
0 10 1
5 1 1
12 -1 2
15 -1 2
-10 5 2
Output
1
Input
5 1
10 9 1
100 99 1
99 -10 1
50 40 1
998233 -10000 1
Output
-1
Note

在样例一中,第 $$$2$$$ 秒时,$$$1$$$ 号车与 $$$3$$$ 号车已经相撞,因此你需要告诉鸡哥的时间是 $$$1$$$。

在样例二中,所有车辆都是同一型号,玩家永远也发现不了这个bug。

加入题单

上一题 下一题 算法标签: