Поликарп учится в Берляндском государственном университете. Совсем скоро ему предстоит сдать сессию. Он должен сдать \(n\) экзаменов.
Для каждого экзамена \(i\) известны два дня: \(a_i\) — день основной сдачи экзамена, \(b_i\) — день пересдачи (\(a_i < b_i\)). В один день Поликарп может сдавать не более одного экзамена. Для каждого экзамена Поликарп самостоятельно выбирает, в какой из двух дней его сдать. Необходимо сдать все \(n\) экзаменов.
Поликарп хочет сдать сессию как можно быстрее. Выведите минимальный номер дня, в который Поликарп сможет сдать все \(n\) экзаменов, либо выведите -1, если сдать сессию полностью невозможно.
Выходные данные
Если Поликарп не сможет сдать все \(n\) экзаменов, выведите -1. В противном случае выведите минимальный номер дня, когда Поликарп сможет это сделать.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
1 5
1 7
|
5
|
|
2
|
3
5 13
1 5
1 7
|
7
|
|
3
|
3
10 40
40 80
10 80
|
80
|
|
4
|
3
99 100
99 100
99 100
|
-1
|