Кондиционеры
(Время: 1 сек. Память: 16 Мб Сложность: 35%)
При реализации проекта «Умная школа» было решено в каждый учебный класс выбранной для этого школы установить по кондиционеру нового поколения для автоматического охлаждения и вентиляции воздуха. По проекту в каждом классе должен быть установлен только один кондиционер и мощность кондиционера должна быть достаточной для размеров класса. Чем больше класс, тем мощнее должен быть кондиционер.
Все классы школы пронумерованы последовательно от 1 до n. Известно, что для каждого класса с номером i, требуется ровно один кондиционер, мощность которого больше или равна ai ватт.
Администрации школы предоставили список из m различных моделей кондиционеров, которые можно закупить. Для каждой модели кондиционера известна его мощность и стоимость. Требуется написать программу, которая определит, за какую минимальную суммарную стоимость кондиционеров можно оснастить все классы школы.
Входные данные
Первая строка входного файла INPUT.TXT содержит одно целое число n (1 ≤ n ≤ 50 000) – количество классов в школе.
Вторая строка содержит n целых чисел ai (1 ≤ ai ≤ 1000) – минимальная мощность кондиционера в ваттах, который можно установить в классе с номером i.
Третья строка содержит одно целое число m (1 ≤ m ≤ 50 000) – количество предложенных моделей кондиционеров.
Далее, в каждой из m строк содержится пара целых чисел bj и cj (1 ≤ bj ≤ 1000, 1 ≤ cj ≤ 1000) – мощность в ваттах j-й модели кондиционера и его цена в рублях соответственно.
Выходные данные
Выходной файл OUTPUT.TXT должен содержать одно число – минимальную суммарную стоимость кондиционеров в рублях. Гарантируется, что хотя бы один корректный выбор кондиционеров существует, и во всех классах можно установить подходящий кондиционер.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 1
800
1
800 1000 | 1000 |
| 2 | 3
1 2 3
4
1 10
1 5
10 7
2 3 | 13 |
Пояснения к примерам
В первом примере нужно купить один единственно возможный кондиционер за 1000 рублей.
Во втором примере оптимально будет установить в первом и втором классах кондиционеры четвертого типа, а в третьем классе – кондиционер третьего типа. Суммарная стоимость этих кондиционеров будет составлять 13 рублей (3 + 3 + 7).
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
