Оргкомитет городского фестиваля готовит расписание премьерных показов. Для каждого фильма известны два дня:

• a_i — день, в который фильм должен быть указан в официальной афише;
• b_i — более ранний день, когда показ тоже можно провести, если это удобно для расписания.

После завершения подготовки все фильмы должны идти в порядке неубывания дней, в которые они фактически будут показаны.

Кроме того, порядок фильмов в афише определяется днями a_i: если у одного фильма день афиши меньше, чем у другого, то и рассматривать их нужно раньше.

Для каждого фильма нужно выбрать один из двух дней показа:

• либо a_i,
• либо b_i.

Требуется сделать так, чтобы день последнего фактического показа был как можно меньше.

Входные данные

В первой строке дано одно целое число n — количество фильмов.

В следующих n строках записано по два целых числа a_i и b_i — день в афише и возможный более ранний день показа.

Выходные данные

Выведите одно целое число — минимально возможный день последнего фактического показа.

Ограничения

• 1 <= n <= 5000
• 1 <= b_i <= a_i <= 10^9

Пример 1

Входные данные

4
1 1
2 1
2 2
4 3

Выходные данные

3

Пример 2

Входные данные

3
5 1
6 2
7 3

Выходные данные

3

Пример 3

Входные данные

5
3 1
3 2
4 4
6 5
6 6

Выходные данные

6

Пояснение

В первом примере можно выбрать фактические дни показов 1, 1, 2, 3. Тогда порядок не нарушается, а последний показ пройдет в день 3.

Во втором примере каждый следующий фильм можно провести в более ранний день, и получится расписание 1, 2, 3.

В третьем примере после некоторых выборов более ранний день уже может нарушить порядок, поэтому часть фильмов приходится оставлять на день из афиши.