给定若干区间,区间之间可能会有部分互相覆盖,也可能一个区间包含另一个区间。
再给定每个区间中要求选出的数字的数量,用(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≤1000,0≤Li≤Ri≤1000,1≤Ci≤Ri-Li+1。