В отеле есть традиция устраивать публичное вечернее кормление всех живущих в отеле кошек. Всего в нём живёт \(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 < n)\) — количество котиков, толкающих своего соседа.
Каждая из последующих \(m\) строк содержит два числа \(k_i\) \((1 \le k_i < n)\) и \(q_{k_i}\) \((1 \le q_{k_i} \le 10^6)\), обозначающую, что если \(k_i\) котик толкается, то общая милота ужина уменьшается на \(q_{k_i}\).
Формат выходных данных
В качестве ответа выведите одно число — максимально возможную милоту ужина.
В первом примере можно отсадить первого питомца к общей миске, а остальных отправить ужинать за свои миски. Суммарная милота благодаря тому, что котики кушают за своими мисками, будет равна \(20 + 30 + 40 + 50 = 140\), но третий котик будет толкать четвертого, поэтому из этой суммы вычитается \(q_3 = 25\). Таким образом, ответ на этот пример равен \(115\).
| № | Входные данные | Выходные данные |
|
1
|
5
10 20 30 40 50
2
1 150
3 25
|
115
|
|
2
|
6
1 7 4 1 2 2
3
1 5
3 3
5 1
|
14
|