题目描述

题目译自 Open Olympiad in Informatics 2017 Day2 T3 「Застройка мегаполиса / Metropolis Development」。

在 $20yy$ 年，莫斯科的建设密度达到了极致，城市范围内几乎没有可用于新建建筑的土地。为了寻找新的收入来源，市政府制定了一项计划，将城市范围内的所有铁路改建为地下铁路，并将释放出来的地面用于商业租赁。

未来建设的规划始于一段长为 $k$ 米的十月铁路段。由于在形成的隧道上方建造建筑物是一个漫长而复杂的过程，决定将新地段分配给最受欢迎的移动餐饮点，如销售冰淇淋、热狗、咖啡等。

用于建设的地段被划分为 $k$ 个等长的段，依次编号为从 $1$ 到 $k$ 的整数。在政府收到的 $n$ 份申请中，第 $i$ 份申请要求分配从 $l_i$ 到 $r_i$ 的段，并且相应的餐饮点将对该段地面施加 $p_i$ 的压力。政府可以拒绝或完全批准每份申请，即为申请的餐饮点分配其请求的所有段。

市政府希望将每个新形成的地面段至少租赁给一个餐饮点。同时，为了降低隧道塌陷的风险，决定最小化任何段上施加的最大压力。注意，允许将一个段同时租赁给多个餐饮点，但在这种情况下，这些餐饮点对该段地面的压力将会累加。

请帮助政府批准一组申请，确保每个段都被至少一个移动餐饮点租赁，同时使隧道地面上的最大压力尽可能小。

输入格式

输入数据的第一行包含两个整数 $n$ 和 $k$ $(1 \leq n \leq 100000, 1 \leq k \leq 10^{9})$，分别表示申请开设餐饮点的数量和地面段的数量。

接下来的 $n$ 行描述申请，每行包含三个整数 $l_i, r_i, p_i$ $(1 \leq l_i \leq r_i \leq 10^{9}, 1 \leq p_i \leq 10^{9})$，分别表示企业申请的段范围和对隧道地面施加的压力。

输出格式

输出可能的最小最大压力，即在所有隧道地面段都被租赁的情况下，餐饮点对隧道地面施加的最大压力。如果无法覆盖整个地段，则输出 $-1$。

3 4
1 3 1
3 4 2
1 4 5

3

在第一个样例中，最优解是批准前两个申请，此时最大压力为 $3$，在第三段上达到。

1 3
1 2 1

-1

在第二个样例中，无法将第三段租赁出去。

4 5
1 4 3
4 5 5
1 1 3
1 2 1

8

在第三个样例中，其中一个最优解是批准所有申请，此时最大压力为 $8$，在第四段上达到。注意，不要求最小化或最大化批准的申请数量。

4 5
1 4 1
4 5 1
3 4 1
5 5 1

1

在第四个样例中，最优解是批准第一份和第四份申请，此时所有段上的压力均为 $1$。

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。