22549번 - 友だちの誘い方 다국어

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

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

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

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

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

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

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

N
a1 b1
a2 b2
.
.
.
aN bN

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

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

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