Intervals

You are given $n$ closed integer intervals $[a_i, b_i]$ together with $n$ integers $c_1, c_2, \dots, c_n$.

Write a program that:

• reads the number of intervals $n$, the two endpoints of each interval, and the integers $c_1, \dots, c_n$ from standard input,
• computes the minimum size of a set $Z$ of integers that shares at least $c_i$ common elements with the interval $[a_i, b_i]$ for every $i = 1, 2, \dots, n$,
• writes that value to standard output.

In other words, minimize $|Z|$ subject to $|Z \cap [a_i, b_i]| \ge c_i$ for every $i$.

The first line contains the number of intervals $n$ $(1 \le n \le 50000)$.

Each of the next $n$ lines describes one interval. The $(i+1)$-th line contains three integers $a_i$, $b_i$, and $c_i$ separated by single spaces, with $0 \le a_i \le b_i \le 50000$ and $1 \le c_i \le b_i - a_i + 1$.

Output a single integer: the minimum size of a set $Z$ that shares at least $c_i$ elements with the interval $[a_i, b_i]$ for every $i = 1, 2, \dots, n$.