F2. Микротранзакции (усложненная версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Единственное отличие между легкой и сложной версиями — ограничечния.

Иван играет в компьютерную игру, содержащую микротранзакции для улучшения внешнего вида персонажей. Так как Иван хочет, чтобы его персонаж выглядел очень круто, он хочет использовать некоторые из этих микротранзакций — и он не хочет начинать играть до того момента, пока не получит их все.

Каждый день (с утра) Иван зарабатывает ровно один бурль.

Всего в игре есть $$$n$$$ типов микротранзакций. Каждая микротранзакция обычно стоит $$$2$$$ бурля и $$$1$$$ бурль, если она на распродаже. Иван хочет использовать ровно $$$k_i$$$ микротранзакций $$$i$$$-го типа (он покупает микротранзакции вечером).

Иван может использовать любое (возможно, нулевое) количество микротранзакций любых типов в течение любого дня (конечно, если ему хватает денег, чтобы это сделать). Если микротранзакция, которую он хочет использовать, находится на распродаже, то он может использовать ее за $$$1$$$ бурль, иначе он может использовать ее за $$$2$$$ бурля.

Также в игровом магазине есть $$$m$$$ специальных предложений. $$$j$$$-е предложение $$$(d_j, t_j)$$$ означает, что микротранзакции $$$t_j$$$-го типа находятся на распродаже в течение $$$d_j$$$-го дня.

Иван хочет использовать все микротранзакции как можно раньше. Ваша задача — найти минимальный номер дня, когда он сможет использовать все микротранзакции, которые он хочет, и действительно сможет начать играть.

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

Первая строка входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — количество типов микротранзакций и количество специальных предложений в игровом магазине.

Вторая строка входных данных содержит $$$n$$$ целых чисел $$$k_1, k_2, \dots, k_n$$$ ($$$0 \le k_i \le 2 \cdot 10^5$$$), где $$$k_i$$$ означает количество копий микротранзакции $$$i$$$-го типа, которое Иван хочет использовать. Гарантируется, что сумма всех $$$k_i$$$ не меньше $$$1$$$ и не больше $$$2 \cdot 10^5$$$.

Следующие $$$m$$$ строк содержат специальные предложения. $$$j$$$-я из этих строк содержит $$$j$$$-е специальное предложение. Оно задано в виде пары целых чисел $$$(d_j, t_j)$$$ ($$$1 \le d_j \le 2 \cdot 10^5, 1 \le t_j \le n$$$) и означает, что микротранзакции $$$t_j$$$-го типа находятся на распродаже в течение $$$d_j$$$-го дня.

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

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

Примеры
Входные данные
5 6
1 2 0 2 0
2 4
3 3
1 5
1 2
1 5
2 3
Выходные данные
8
Входные данные
5 3
4 2 1 3 2
3 5
4 2
2 5
Выходные данные
20