구간

정수로 이루어진 닫힌 구간 $[a_i, b_i]$ 가 $n$개 주어지고, 정수 $c_1, c_2, \dots, c_n$ 이 함께 주어진다.

다음을 수행하는 프로그램을 작성하시오.

• 구간의 개수 $n$, 각 구간의 두 끝점, 그리고 정수 $c_1, \dots, c_n$ 을 표준 입력에서 읽는다.
• 모든 $i = 1, 2, \dots, n$ 에 대하여 구간 $[a_i, b_i]$ 와 공통 원소를 적어도 $c_i$ 개 갖는 정수 집합 $Z$ 의 최소 크기를 구한다.
• 그 값을 표준 출력에 출력한다.

즉, 모든 $i$ 에 대해 $|Z \cap [a_i, b_i]| \ge c_i$ 를 만족하면서 $|Z|$ 를 최소화하면 된다.

첫째 줄에 구간의 개수 $n$ $(1 \le n \le 50000)$ 이 주어진다.

이어지는 $n$개의 줄에 각 구간의 정보가 주어진다. $i+1$번째 줄에는 세 정수 $a_i$, $b_i$, $c_i$ 가 공백 하나로 구분되어 주어지며, $0 \le a_i \le b_i \le 50000$ 이고 $1 \le c_i \le b_i - a_i + 1$ 을 만족한다.

모든 $i = 1, 2, \dots, n$ 에 대하여 구간 $[a_i, b_i]$ 와 원소를 적어도 $c_i$ 개 공유하는 집합 $Z$ 의 최소 크기를 정수 하나로 출력한다.