← 返回题目列表

Codeforces · 822/C

C. 黑客,收拾行李吧!

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

众所周知,分散注意力的最好方法就是做自己最喜欢的事情。对于勒哈来说,工作就是这样的事情。

于是黑客为了摆脱无聊开始努力工作。这意味着Leha开始入侵世界各地的计算机。由于如此热心,老板给了黑客整整x天的假期。要知道大多数人都喜欢去某个地方度假,所以Leha立即去了旅行社。在那里他发现还剩下n张优惠券。第 i 张代金券由三个整数 li、ri、costi 表示——从 Vičkopolis 出发的日期、返回 Vičkopolis 的日期以及相应的代金券费用。第 i 张优惠券的持续时间为值 ri - li + 1。

同时,Leha 希望将自己的职业分成两部分。此外,他想花尽可能少的钱。形式上,Leha 希望恰好选择两张凭证 i 和 j(i ≠ j),以便它们不相交,它们的持续时间之和恰好为 x,并且它们的总成本尽可能小。如果至少满足以下条件之一,则两张凭证 i 和 j 不相交:ri < lj 或 rj < li。

帮助Leha选择必要的优惠券!

输入

第一行包含两个整数n和x (2 ≤ n, x ≤ 2·105) — 旅行社的优惠券数量和相应的Leha 假期时长。

接下来的 n 行每行包含三个整数 li、ri 和 costi (1 ≤ li ≤ ri ≤ 2·105, 1 ≤ costi ≤ 109) — 凭证的描述。

输出

打印一个整数 - Leha 将花费的最小金额,或者如果无法选择总持续时间恰好为 x 的两张不相交的凭证,则打印 - 1。

示例

输入 #1

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

输出 #1

5

输入 #2

3 2
4 6 3
2 4 1
3 5 4

输出 #2

-1

注意

在第一个示例中,Leha 应选择第一张和第三张优惠券。因此,总持续时间将等于 (3 - 1 + 1) + (6 - 5 + 1) = 5,总成本将为 4 + 1 = 5。

在第二个示例中,每张优惠券的持续时间为 3,因此不可能选择总持续时间等于 2 的两张优惠券。