众所周知,分散注意力的最好方法就是做自己最喜欢的事情。对于勒哈来说,工作就是这样的事情。
于是黑客为了摆脱无聊开始努力工作。这意味着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 的两张优惠券。