区间

区间

测试数据来自 system/1532

描述

对于一个整数序列,给出的一个三元组[a,b,c]表示该序列在闭区间[a,b]的整数至少有c个,其中a,b,c均为整数。

题目将给出n个三元组,求同时满足这n个三元组的序列的最少元素个数是多少。如果不存在这样的满足要求的序列,则输出-1。

格式

输入格式

第一行一个整数n(n<=50000),表示区间个数。

接下来n行,每行三个整数a,b,c(0<=a<=b<=50000,1<=c<=b-a+1),用一个空格隔开,意义如题目描述。

输出格式

一个数,即为答案

样例1

样例输入1

5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1

样例输出1

6

限制

每个测试点1s

提示

由于官方数据不全,所以有几个点是自己做的
样例说明:
满足条件的最少元素序列:3,4,5,8,9,10
[3,7]中有3,4,5三个数
[8,10]中有8,9,10三个数
……

来源

zju

信息

ID
1006
难度
(无)
分类
图结构 | 差分约束贪心 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
上传者