2518 - 区间选数

题目描述

给定若干区间,区间之间可能会有部分互相覆盖,也可能一个区间包含另一个区间。

再给定每个区间中要求选出的数字的数量,用(L_i,R_i,C_i)表示要从[L_i,R_i]区间中选出至少C_i个整数。

请问,如果要满足所有区间选数数量的要求,至少一共要选多少个数?

输入

第一行一个整数 N ,表示区间个数;

接下来 N 行,每行三个整数(L_i,R_i,C_i),含义如题所述。

输出

输出一个整数,表示最少要选出数字的数量。

样例

输入

4
4 5 1
6 10 3
7 10 3
5 6 1

输出

4
说明

【样例解释】

区间 [4,5] 中选择数字 5

区间 [5,6] 不需要再选,5 已经被选中 。

区间 [6,10] 中选择数字 7,8,9 或者数字 8,9,10

区间 [7,10] 中由于上一个 [6,10] 中已经选择了 7,8,9 或者 数字 8,9,10 ,因此不需要再选择。

一共选择了 4 个数。

【数据范围】

N≤10000≤L_i≤R_i≤10001≤C_i≤R_i-L_i+1

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 365
通过人数 200
金币数量 1 枚
难度 入门


上一题 下一题