408565: GYM103186 H 鸡哥的 AI 驾驶

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

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

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

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

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

第一行有两个整数 $$$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$$$ 辆车的位置、速度和型号。

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

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

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

5 2
0 10 1
5 1 1
12 -1 2
15 -1 2
-10 5 2

1

5 1
10 9 1
100 99 1
99 -10 1
50 40 1
998233 -10000 1

-1

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

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