# 2919. Intervals

You are given $n$ closed, integer intervals $[a_i, b_i]$ and $n$ integers $c_1, \ldots, c_n$.

Write a program that:

• reads the number of intervals, their end points and integers $c_1, \ldots, c_n$ from the standard input,
• computes the minimal size of a set $\mathscr{Z}$ of integers which has at least $c_i$ common elements with interval $[a_i, b_i]$, for each $i=1,2,\ldots,n$,
• writes the answer to the standard output.

### 输入格式

The first line of the input contains an integer $n$ $(1 \leq n \leq 50~000)$ – the number of intervals. The following $n$ lines describe the intervals. The $(i+1)$-th line of the input contains three integers $a_i, b_i$ and $c_i$ separated by single spaces and such that $0 \le a_i \le b_i \le 50~000$ and $1 \le c_i \le b_i - a_i+1$.

### 输出格式

The output contains exactly one integer equal to the minimal size of set $\mathscr{Z}$ sharing at least ci elements with interval $[a_i, b_i]$, for each $i=1,2,\ldots,n$.

### 样例

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

Output
6


2 人解决，4 人已尝试。

2 份提交通过，共有 7 份提交。

9.1 EMB 奖励。