ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs ContestProblemSetList
Login Register

问题 F: zz旅行2

内存限制：256 MB 时间限制：1 S
题面：传统 评测方式：文本比较 上传者：
提交：139 通过：47
返回比赛提交提交记录

题目描述

  ZZ是一名非常厉害的黑客，这意味着ZZ可以在全世界范围内入侵电脑。由于ZZ非常出色，老板给他放了整整X天的假。你知道大多数人都喜欢去某个地方度假，所以ZZ立即去了旅行社。在那里，他发现还有n张旅行卷。第i张旅券的特征是三个整数li, ri, costi ——从杭州出发的日子、回到杭州日子以及相应的费用。第i张旅券的持续时间是一个值ri - li + 1。

  同时，ZZ想把自己的假期分成两部分。此外，他想尽可能少花钱。从形式上看，ZZ想准确地选择两个旅行券i和j（i ≠ j），使它们不相交，它们的持续时间之和正好是x，并且它们的总成本尽可能地小。两个旅券i和j不相交，需要至少满足以下条件之一，则：ri < lj或rj < li。
帮助ZZ选择必要的旅券!

输入格式

第一行包含两个整数n和x（2 ≤ n，x ≤ 2*10^5）——旅行社里的旅游线路数量和ZZ的假期时间。
接下来的n行包含三个整数li、ri和costi（1 ≤ li ≤ ri ≤ 2*10^5，1 ≤ costi ≤ 10^9）——每条旅游线路的值。

输出格式

打印一个整数——ZZ将花费的最小金额，如果不可能选择总时长正好为x的两个不相交的旅券，则打印-1。
Input 
4 5
1 3 4
1 2 5
5 6 1
1 2 4
Output 
5
Input 
3 2
4 6 3
2 4 1
3 5 4
Output 
-1
Note
在第一个例子中，ZZ应选择第一张和第三张代金券。此后，总持续时间将等于（3-1+1）+（6-5+1）=5，并且总成本将为4+1=5。
在第二个例子中，每张代金券的持续时间为3，因此不可能选择两张总持续时间等于2的代金券。


输入样例 复制 

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

输出样例 复制 

5

数据范围与提示

注意
在第一个样本里，利哈应选择第一和第三个券。至此，总存续期为(3-1+1)+(6-5+1)=5，总成本为4+1=5。
在第二个样本中，每个券的持续时间为3，因此不可能选择两个总持续时间为2的券。

分类标签