Remote Training on Programming

При реализации проекта «Умная школа» было решено в каждый учебный класс выбранной для этого школы установить по кондиционеру нового поколения для автоматического охлаждения и вентиляции воздуха. По проекту в каждом классе должен быть установлен только один кондиционер и мощность кондиционера должна быть достаточной для размеров класса. Чем больше класс, тем мощнее должен быть кондиционер.

Все классы школы пронумерованы последовательно от 1 до n. Известно, что для каждого класса с номером i, требуется ровно один кондиционер, мощность которого больше или равна a_i  ватт.

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

Формат входного файла

Первая строка входного файла содержит одно целое число n (1 ≤ n ≤ 50 000) ‑ количество классов в школе.

Вторая строка содержит n целых чисел a_i (1 ≤ a_i ≤ 1000) ‑ минимальная мощность кондиционера в ваттах, который можно установить в классе с номером i.

Третья строка содержит одно целое число m (1 ≤ m ≤ 50 000) ‑ количество предложенных моделей кондиционеров.

Далее, в каждой из m строк содержится пара целых чисел b_j и c_j (1 ≤ b_j ≤ 1000, 1 ≤ c_j ≤ 1000) ‑ мощность в ваттах j-й модели кондиционера и его цена в рублях соответственно.

Формат выходного файла

Выходной файл должен содержать одно число ‑ минимальную суммарную стоимость кондиционеров в рублях. Гарантируется, что хотя бы один корректный выбор кондиционеров существует, и во всех классах можно установить подходящий кондиционер.

Примеры входных и выходных файлов

Входные данные	Выходные данные
1 800 1 800 1000	1000
3 1 2 3 4 1 10 1 5 10 7 2 3	13

Пояснения к примерам

В первом примере нужно купить один единственно возможный кондиционер за 1000 рублей.

Во втором примере оптимально будет установить в первом и втором классах кондиционеры четвертого типа, а в третьем классе – кондиционер третьего типа. Суммарная стоимость этих кондиционеров будет составлять 13 рублей (3 + 3 + 7).

Система оценивания

Частичные решения для n, m ≤ 1000 будут оцениваться из 50 баллов.