← 返回题目列表

Codeforces · 1555/E

E. 镗刀段

中文机器翻译题面 查看原题

在数轴上给定 $$$n$$$ 段,编号从 $$$1$$$ 到 $$$n$$$。第 $$$i$$$ 段涵盖从 $​​$$l_i$$$ 到 $$$r_i$$$ 的所有整数点,并具有值 $$$w_i$$$。

系统会要求您选择这些片段的子集(可能是全部)。一旦选择了子集,如果存在覆盖两个整数点的选定线段,则可以在两个整数点之间移动。如果可以从点 $$$1$$$ 开始以任意次数的移动到达点 $$$m$$$,则子集是好的。

子集的成本是其中段的最大值和最小值之间的差。找到一个好的子集的最小成本。

在每个测试中都至少存在一个好的子集。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 3 \cdot 10^5$$$; $$$2 \le m \le 10^6$$$) — 段数和整数点数。

接下来的 $$$n$$$ 行包含三个整数 $$$l_i$$$、$$$r_i$$$ 和 $$$w_i$$$ ($$$1 \le l_i < r_i \le m$$$; $$$1 \le w_i \le 10^6$$$) — 第 $$$i$$$ 段的描述。

在每个测试中都至少存在一个好的子集。

输出

打印一个整数——一个好的子集的最小成本。

示例

输入 #1

5 12
1 5 5
3 4 10
4 10 6
11 12 5
10 12 3

输出 #1

3

输入 #2

1 10
1 10 23

输出 #2

0