Description

There is an integer sequence whose elements are all distinct. We do not know its length (i.e., the number of integers), but we know, for certain intervals, at least how many elements lie within them. Each constraint is described by a triple ($L_i, R_i, C_i$), meaning that at least $C_i$ numbers in the sequence come from the interval $[L_i, R_i]$. Given several such intervals, what is the minimum possible length of this integer sequence?

Input Format

The first line contains an integer $N$, the number of intervals.

Each of the next $N$ lines contains three integers $L_i, R_i, C_i$ describing an interval.

Output Format

Output a single integer: the minimum possible length of the sequence.

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

4

Hint

Constraints

For all testdata, $1 \le N \le 1000$, $0 \le L_i \le R_i \le 1000$, $1 \le C_i \le R_i - L_i + 1$.

Translated by ChatGPT 5