A Way to Invite Friends

時間制限 : 8 sec, メモリ制限 : 65536 KB

Problem B: 友だちの誘い方

明日から、待ちに待った夏休みが始まります。なのでわたしは、友だちを誘って、海に遊びに行くこ とに決めました。

けれども、わたしの友だちには、恥ずかしがりやさんが多いです。その人たちは、あまり多くの人が いっしょに来ると知ったら、きっと嫌がるでしょう。

ほかにも、わたしの友だちには、目立ちたがりやさんも多いです。その人たちは、いっしょに来る人 があまり多くないと知れば、きっと嫌がるでしょう。

それと、わたしの友だちには、いつもは目立ちたがりやなのに実は恥ずかしがりやさんな人もいま す。その人たちは、いっしょに来る人が多すぎても少なすぎても、きっと嫌がるでしょう。

こういうのは、大勢で行った方が楽しいはずです。だからわたしは、できるだけたくさんの友だちを 誘いたいと思っています。けれども、嫌がる友だちを無理やり連れていくのはよくありません。

いったい、わたしは最大で何人の友だちを誘うことができるのでしょうか。

わたしは、こういう頭を使いそうな問題が大の苦手です。なので、あなたにお願いがあります。もし よろしければ、わたしの代わりにこの問題を解いていただけないでしょうか。いえ、決して無理にと は言いません。けれど、もし解いていただるのでしたら、わたしはとても嬉しいです。

Input

N
a1 b1
a2 b2
.
.
.
aN bN

入力の1行目には、整数N(1 ≤ N ≤ 100,000)が書かれている。これは、友だちの数をあらわす。

続くN行には、整数 ai と整数 bi(2 ≤ aibi ≤ 100,001)が、空白区切りで書かれている。1+ i 行目に書かれた整数 aibi は、i 番目の友だちは海に行く人数が ai 人以上 bi 人以下でないと嫌がることをあらわす。海に行く人数には「わたし」も含まれることに注意せよ。

Output

嫌がる友だちが出ないように、海に誘うことのできる友だちの最大人数を出力せよ。

Sample Input 1

4
2 5
4 7
2 4
3 6

Sample output 1

3

Sample Input 2

5
8 100001
7 100001
12 100001
8 100001
3 100001

Sample output 2

0

Sample Input 3

6
2 9
4 8
6 7
6 6
5 7
2 100001

Sample output 3

5

Source: ACM-ICPC Japan Alumni Group Summer Camp 2010 , Day 2, Tokyo, Japan, 2010-09-18
http://acm-icpc.aitea.net/