题目描述

给定 $n$ 个闭区间 [$a$_$i$,$b$_$i$] 和 $n$ 个整数 $c$_$i$。

你需要构造一个整数集合 $Z$ ，使得对于任意的 ∀ $i$ ∈[$1$,$n$]， $Z$ 中满足 $a$_$i$≤ $x$ ≤ $b$_$i$ 的整数 $x$ 不少于 $c$_$i$ 个。

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

输入

第一行包含整数 $n$ 。

接下来 $n$ 行，每行包含三个整数 $a$_$i$,$b$_$i$,$c$_$i$。

数据范围

$1$ ≤ $n$ ≤ $50000$, $0$ ≤ $a$_$i$,$b$_$i$≤ $50000$,

$1$ ≤ $c$_$i$≤ $b$_$i$− $a$_$i$+$1$ ；

输出

输出一个整数表示结果。

样例

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

6

来源

Poj1201