题目描述

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

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

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

输入格式

第一行一个整数 N ，表示区间个数；

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

数据范围

N ≤ 1000

0 ≤ $L_i$ ≤$R_i$ ≤ 1000

1 ≤ $C_i$ ≤ $R_i - L_i + 1$ 。

输出格式

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

样例

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 个数。