Кондиционеры

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

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

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

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

Первая строка входного файла INPUT.TXT содержит одно целое число 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-й модели кондиционера и его цена в рублях соответственно.

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

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

Примеры

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

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

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

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!