В отеле есть традиция устраивать публичное вечернее кормление всех живущих в отеле кошек. Всего в нём живёт $$$n$$$ кошек, и имеется по одной личной миске для каждой из кошек и одна большая общая миска, из которой может наесться любое количество питомцев. Личные миски кошек расположены в один ряд, а общая стоит отдельно от всех остальных.
Ваши питомцы хорошо обучены есть строго либо из своей миски, либо из большой общей миски. Когда $$$i$$$-й котик ест из своей миски, то он выглядит милым на некоторую величину $$$a_i$$$. Если бы все котики спокойно кушали из своей миски, то общая милота ужина вычислялась бы как сумма $$$a_i$$$ всех котиков.
Но не все так просто, некоторые питомцы слишком увлекаются едой и начинают толкать своего соседа справа во время трапезы, тем самым мешая другим кушать и портя общую милоту ужина. Допустим, вы знаете, что $$$i$$$-й котик толкается, тогда вы можете избежать толкания, если посадить либо $$$i$$$-го котика, либо $$$i+1$$$-го котика ужинать за общую миску, но в таком случае отсаженный котик уже не будет привносить милоту в общую милоту ужина. Вам известно, что толкание $$$i$$$-го котика своего соседа справа отнимает $$$q_i$$$ общей милоты ужина. Таким образом, общая милота ужина вычисляется как сумма милоты всех котиков, которые ужинают за своей миской, из которой вычитаются все $$$q_i$$$ котиков, которые толкают своего соседа на позиции $$$i+1$$$.
Сегодня в отель заселились очень важные гости, и вы хотите посадить котиков ужинать так, чтобы общая милота ужина была максимальной.
Первая строка содержит одно целое число $$$n$$$ $$$(1 \le n \le 10^6)$$$ — количество котиков.
Вторая строка содержит $$$n$$$ целых чисел $$$(1 \le a_i \le 10^6)$$$, где $$$a_i$$$ — милота $$$i$$$-го котика.
Третья строка содержит одно число $$$m$$$ $$$(0 \le m \lt n)$$$ — количество котиков, толкающих своего соседа.
Каждая из последующих $$$m$$$ строк содержит два числа $$$k_i$$$ $$$(1 \le k_i \lt n)$$$ и $$$q_{k_i}$$$ $$$(1 \le q_{k_i} \le 10^6)$$$, обозначающую, что если $$$k_i$$$ котик толкается, то общая милота ужина уменьшается на $$$q_{k_i}$$$.
В качестве ответа выведите одно число — максимально возможную милоту ужина.
5 10 20 30 40 50 2 1 150 3 25
115
6 1 7 4 1 2 2 3 1 5 3 3 5 1
14
В первом примере можно отсадить первого питомца к общей миске, а остальных отправить ужинать за свои миски. Суммарная милота благодаря тому, что котики кушают за своими мисками, будет равна $$$20 + 30 + 40 + 50 = 140$$$, но третий котик будет толкать четвертого, поэтому из этой суммы вычитается $$$q_3 = 25$$$. Таким образом, ответ на этот пример равен $$$115$$$.
