시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 25 | 16 | 12 | 60.000% |
При реализации проекта «Умная школа» было решено в каждый учебный класс выбранной для этого школы установить по кондиционеру нового поколения для автоматического охлаждения и вентиляции воздуха. По проекту в каждом классе должен быть установлен только один кондиционер и мощность кондиционера должна быть достаточной для размеров класса. Чем больше класс, тем мощнее должен быть кондиционер.
Все классы школы пронумерованы последовательно от 1 до n. Известно, что для каждого класса с номером i, требуется ровно один кондиционер, мощность которого больше или равна ai ватт.
Администрации школы предоставили список из m различных моделей кондиционеров, которые можно закупить. Для каждой модели кондиционера известна его мощность и стоимость. Требуется написать программу, которая определит, за какую минимальную суммарную стоимость кондиционеров можно оснастить все классы школы.
Первая строка входного файла содержит одно целое число 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-й модели кондиционера и его цена в рублях соответственно.
Выходной файл должен содержать одно число - минимальную суммарную стоимость кондиционеров в рублях. Гарантируется, что хотя бы один корректный выбор кондиционеров существует, и во всех классах можно установить подходящий кондиционер.
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).