题目描述

给定 n个区间 [ai,bi]和 n个整数 ci。

你需要构造一个整数集合 Z，使得 ∀i∈[1,n]，Z中满足 ai≤x≤bi的整数 x不少于 ci个。

求这样的整数集合 Z最少包含多少个数。

输入格式

第一行包含整数 n。

接下来 n行，每行包含三个整数 ai,bi,ci。

输出格式

输出一个整数表示结果。

样例

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

6

提示

1≤n≤50000,

0≤ai,bi≤50000，

0≤ci≤bi−ai+1