Description

Original source: Southwestern Europe 2002, problem statement can be found at POJ 1201.

Given $n$ closed intervals $[a_i, b_i]$ and $n$ integers $c_i$, you need to construct an integer set $Z$ such that for any $i\in [1,n]$, the number of integers $x$ in $Z$ that satisfy $a_i\le x\le b_i$ is at least $c_i$. Find the minimum number of integers that such a set $Z$ must contain.

In simpler terms, select as few integers as possible from the range $0\sim 5\times 10^4$ such that each interval $[a_i, b_i]$ contains at least $c_i$ selected integers.

Input Format

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

The following $n$ lines describe the intervals. The $(i+1)$-th line contains three integers $a_i, b_i, c_i$, separated by spaces.

Output Format

A single line outputting the minimum number of integers required to meet the conditions.

Sample 1

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

6

Data Range and Hints

For all data, $1\le n\le 5\times 10^4$, $0\le a_i\le b_i\le 5\times 10^4$, and $1\le c_i\le b_i-a_i+1$.