问题 1324. -- 火聚聚铺地毯

1324: 火聚聚铺地毯

时间限制: 1 Sec  内存限制: 128 MB
提交: 127  解决: 38
[提交][状态][讨论版]

题目描述

火聚聚在准备一场晚宴,他的一个计划是在一段坐标为M到E(包含M和E)的路径中铺上红地毯,但是这段路径太长了,一张地毯可能不够,他可能得用若干地毯合起来才能把它铺满,他找到了一位神奇的地毯商,地毯商有N块神奇的地毯,每块地毯可以铺满坐标T1到T2的范围(包含T1T2),花费为S,地毯不能移动,火聚聚希望选取若干数量的地毯,使得在铺满整个范围(即范围内每个坐标都至少包含于一个地毯中)的情况下花费最少

输入

单组数据

第一行三个数字N, M, E(N <= 1e5 , 1 <= M <= E <= 1e18)

之后N行每行三个数字T1, T2, S(M <= T1 <= T2 <= E , S <= 1e4)

输出

 一个数字,代表最小花费,如果无论如何都无法铺满,输出-1

(数据保证结果在int范围内)

样例输入

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

样例输出

5

提示

 选用第一个区间覆盖了1, 2, 3三个点,第二个区间覆盖了4, 5两个点,第三个区间只覆盖了1点,没有必要选中,所以结果是2+3=5

来源

[提交][状态][讨论版]