I - Hamming

問題

コーラス会場に人が $N$ 人並んでいます。
人 $i$ の「歌のうまさ」は $i$ です。

人 $i$ はそれぞれ「歌」と「ハミング」のどちらかを選択します。
コーラスを始めたあと、人 $i$ は「歌」を選んだならば「歌」を選んだ人中で自分より「歌のうまさ」が大きい人が $A_i$ 人以上いるか、自分より「歌のうまさ」が小さい人が $B_i$ 人未満だと逃げます。

全員が逃げなかったとき、最大で何人が「歌」を選んだかを出力してください。

制約

• $1\leq N\leq 200000$
• $0< A_i\leq N$
• $0\leq B_i< N$
• 入力はすべて整数

$A_i, B_i$ の不等号に注意してください。

小課題

1. (12 点) $1\leq N\leq 20$
2. (18 点) $1\leq N\leq 1000, A_i\leq 2, B_i = 0$
3. (30 点) $1\leq N\leq 1000, B_i = 0$
4. (12 点) $1\leq N\leq 1000$
5. (28 点) $B_i = 0$
6. (50 点) 追加の制約はない

入力

$N$
$A_1\quad B_1$
$A_2\quad B_2$
$\vdots\quad \vdots$
$A_{N-1}\quad B_{N-1}$
$A_N\quad B_N$

入力例1

3
3 0
3 1
2 2
Copy

出力例1

3
Copy

全員が歌っても問題ないです。