题目描述

给定$n$个闭区间$[a_i,b_i]$和$n$个整数$c_1,...,c_n$。要求编写程序：

1. 从标准输入读取区间数量、端点值及整数$c_i$
2. 计算满足以下条件的最小整数集$Z$的大小：对于每个区间$[a_i,b_i]$，$Z$与该区间至少有$c_i$个公共元素
3. 输出结果至标准输出

输入格式

• 第一行：$n$（区间数量，$1 \leq n \leq 50000$）
• 随后$n$行：每行三个整数$a_i,b_i,c_i$（$0 \leq a_i \leq b_i \leq 50000$，$1 \leq c_i \leq b_i-a_i+1$）

输出格式

一个整数，表示满足条件的最小集合$Z$的大小

样例输入

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

样例输出

6

题目来源

2002年西南欧地区竞赛