4480 - 第十课:最小整数集合

给出n个三元组$ a_i, b_i, c_i $。要求选择最小的整数集合$ Z $,使得对于每一个三元组,$ Z $中至少有$ c_i $个元素在$ [a_i, b_i] $区间内。
 

输入

第一行输入一个整数$ n(1 \le n \le 5 \cdot 10^4)$。
接下来n行,每行给出三元组$ a_i, b_i, c_i(0 \le a_i \le b_i \le 5 \cdot 10^4, 1 \le c_i \le b_i - a_i + 1) $。
 

输出

输出最小集合$ Z $的大小。

样例

输入

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

输出

6
时间限制 5 秒
内存限制 128 MB
统计
上一题 下一题