题目描述

有一个整数序列，它的每个数各不相同，我们不知道它的长度是多少（即整数个数），但我们知道在某些区间中间至少有多少个整数，用区间（$L_i,R_i,C_i$）来描述，表示这个整数序列中至少有 $C_i$ 个数来自区间 $[L_i,R_i]$，给出若干个这样的区间，问这个整数序列的长度最少能为多少？

输入格式

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

接下来 $N$ 行，每行三个整数 $L_i,R_i,C_i$，描述一个区间。

输出格式

仅一个数，表示该整数序列的最小长度。

输入样例 #1

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

输出样例 #1

4

输入样例 #2

6
10 10 1
9 14 2
12 13 2
6 8 2
3 5 3
15 17 2

输出样例 #2

10

输入样例 #3

7
0 2 1
14 16 2
3 7 5
20 20 1
11 13 3
9 9 1
8 15 6

输出样例 #3

13

数据范围与约定

数据范围及约定

对于全部数据，$1\le N \le 1000$，$0 \le L_i \le R_i \le 1000$，$1 \le C_i \le R_i-L_i+1$。