Паша участвует в соревновании по программированию на одном небезызвестном сайте. На этот раз он настроен на победу и сделает всё возможное, чтобы достичь её!
На этом соревновании есть n задач, задачу с номером i Паша решает гарантированно верно за ai единиц времени. В один момент времени он может думать только над одной задачей из списка. Решение по задаче на сайт он отправляет мгновенно. Паша может отправлять сколько угодно решённых им задач в один момент времени.
Но сайт, на котором проходит соревнование, не выдерживает очень большое количество участников, поэтому он работает далеко не всегда. Паше поступила информация о том, что сайт будет работать m промежутков времени, j-й промежуток описывается своими границами времени lj и rj. Отправить задачу Паша может только в те моменты времени, когда сайт работает. Иными словами, Паша может отправить решение в момент времени T в том случае (и только в том случае), если существует такой промежуток x, что lx ≤ T ≤ rx.
Так как Паша очень хочет победить, он захотел узнать свой наилучший результат. Мы должны помочь ему, сказав, в какой минимальный момент времени он сможет сдать все задачи, если будет действовать оптимально, или же сказать, что вне зависимости от выбора стратегии он не успеет этого сделать.
Выходные данные
Если Паша успевает решить и отправить все задачи до конца соревнования, то выведите минимальное время, за которое он сможет это сделать.
Если же Паша не успеет решить и отправить все задачи за отведённое время, выведите «-1» (без кавычек).
Примечание
В первом тесте из условия Паша может сделать так: он сначала решает вторую задачу за 4 единицы времени и сразу же отправляет её, поскольку в этот момент времени сайт работает. После он решает первую задачу ещё за 3 единицы времени и отправляет её в момент времени 7, поскольку тогда начинается второй отрезок времени, когда сайт работает.
Во втором тесте Паша придумывает задачу позже, чем заканчивается последний отрезок времени, когда он мог её отправить.
В третьем тесте Паша успевает послать решение в самом конце промежутка.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
3 4
2
1 4
7 9
|
7
|
|
2
|
1
5
1
1 4
|
-1
|
|
3
|
1
5
1
1 5
|
5
|