A. Соревнование
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Паша участвует в соревновании по программированию на одном небезызвестном сайте. На этот раз он настроен на победу и сделает всё возможное, чтобы достичь её!

На этом соревновании есть n задач, задачу с номером i Паша решает гарантированно верно за ai единиц времени. В один момент времени он может думать только над одной задачей из списка. Решение по задаче на сайт он отправляет мгновенно. Паша может отправлять сколько угодно решённых им задач в один момент времени.

Но сайт, на котором проходит соревнование, не выдерживает очень большое количество участников, поэтому он работает далеко не всегда. Паше поступила информация о том, что сайт будет работать m промежутков времени, j-й промежуток описывается своими границами времени lj и rj. Отправить задачу Паша может только в те моменты времени, когда сайт работает. Иными словами, Паша может отправить решение в момент времени T в том случае (и только в том случае), если существует такой промежуток x, что lx ≤ T ≤ rx.

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

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

В первой строке входных данных содержится целое положительное число n (1 ≤ n ≤ 1000) — количество задач в соревновании. Во второй строке задано n целых положительных чисел ai (1 ≤ ai ≤ 105) — время, которое Паша тратит на решение задачи с номером i.

В третьей строке содержится целое неотрицательное число m (0 ≤ m ≤ 1000) — количество отрезков времени, когда сайт работает. Следующие m строк описывают сами отрезки времени. j-я из них содержит два целых числа lj и rj (1 ≤ lj < rj ≤ 105) — границы j-го отрезка.

Гарантируется, что отрезки не пересекаются и заданы в порядке возрастания времён, то есть для любого j > 1 выполняется условие lj > rj - 1.

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

Если Паша успевает решить и отправить все задачи до конца соревнования, то выведите минимальное время, за которое он сможет это сделать.

Если же Паша не успеет решить и отправить все задачи за отведённое время, выведите «-1» (без кавычек).

Примеры
Входные данные
2
3 4
2
1 4
7 9
Выходные данные
7
Входные данные
1
5
1
1 4
Выходные данные
-1
Входные данные
1
5
1
1 5
Выходные данные
5
Примечание

В первом тесте из условия Паша может сделать так: он сначала решает вторую задачу за 4 единицы времени и сразу же отправляет её, поскольку в этот момент времени сайт работает. После он решает первую задачу ещё за 3 единицы времени и отправляет её в момент времени 7, поскольку тогда начинается второй отрезок времени, когда сайт работает.

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

В третьем тесте Паша успевает послать решение в самом конце промежутка.