题目背景

发光虫很罕见，并且它的寿命非常短。它们常常很孤独，会去寻找其他的伙伴，有时会误认为复制人是新朋友，上下摆动他们的身体来问候复制人。他们也会被发光的东西吸引，可能更容易飞向人造光源或其他发光虫之类的东西。

发光虫有很多种变种，它们相互独立，甚至歧视，所以他们不会靠的太近。

但是同类的发光虫却十分团结，它们永远同仇敌忾。

题目描述

每一种发光虫都有其独特的生活习性，所以每种发光虫的活动范围不尽相同。

复制人建造了一个很大的基地，发光虫幼时会在基地的某一个范围活动，成年后会根据喜好选择一个新的范围生活。

但是领地周围如果有不同种类的发光虫则会发生冲突，减少基地的有序度，有序度过低会使得可爱的发光虫闷闷不乐而加速死亡。

复制人找到了时间法师，他可以帮助复制人让一些发光虫快速成年或者回到幼年，由于复制人不够聪明，所以它们找到了你，希望你能帮助它们最大化基地的有序度。

认为基地的有序度是任意两种发光虫间有序度的最小值，两种发光虫间的有序度则是两种发光虫所有个体间有序度的最小值。

为了简化问题，我们将基地看作一个直线，发光虫活动的范围看做一个点，如果有两只不同种的发光虫分别在 $a, b$ 处，那么它们间的有序度为 $|a - b|$。

题目输入

第一行两个数 $n, k$ 表示发光虫的个数与种类数。

接下来 $n$ 行，每行三个数 $(x_i, y_i, k_i)$ 表示第 $i$ 只发光虫在幼时会生活在 $x_i$ 处，成年后会生活在 $y_i$ 处，它的种类为 $k_i$。

题目输出

为了不写 SPJ，所以只需要输出一个数 $n$ 表示最小可能的有序度即可。

样例

样例 #1

输入

3 2
1 4 1
3 7 1
2 8 2

输出

5

解释

第一种发光虫都处在幼时，第二种则成年，此时有序度为 $8 - 3 = 5$。

数据规模与约定

对于 $5 \%$ 的数据满足 $n \le 20$。

对于另外 $15 \%$ 的数据满足 $n \le 1000$。

对于另外 $20 \%$ 的数据满足 $k \le 5$。

对于另外 $20 \%$ 的数据满足 $k_i$ 互不相同。

对于 $100\%$ 的数据满足 $k \le n \le 1.5 \times 10^4，|x_i|, |y_i| \le 10^9$。

时空限制

512 MB，3s