6587 - 区间

给定n 个闭区间(形如[Ai,Bi],Ai,Bi都为整数)和n个整数C1..Cn。

写一个程序:

在标准输入中输入区间的数目,区间及C1..Cn。

计算一个最小的集合,满足:它对于任意的[Ai,Bi],保证集合中至少含有Ci个公共元素。

将答案输出到屏幕。

输入

第一行包括一个整数n(1<=n<=50000),表示区间数。以下的n行依次描述区间。

第i+1行是三个整数Ai,Bi,Ci,0<=Ai<=Bi<=50000,1<=Ci<=Bi-Ai+1。

输出

输出仅一行,包括一个整数,表示集合中最少的公共元素的个数。

样例

输入

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

输出

6

来源

一本通提高

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题