Снегоуборщики
(Время: 1 сек. Память: 64 Мб Сложность: 52%)
Для дачных участков СНТ необходимо закупить снегоуборщики. Для каждого из N участков будет куплен свой снегоуборщик. Известны минимальные требования к мощности W этой техники для каждого из участков.
Для закупки доступно К моделей снегоуборщиков определённой мощности P и стоимости C. Количество экземпляров каждой модели не ограничено. Для каждого участка выбирается снегоуборщик минимальной стоимости, мощность которого не меньше требуемой; при одной и той же стоимости выбирается модель максимальной мощности.
Требуется определить общую стоимость закупки и максимальную мощность снегоуборщика, входящего в число купленных. Гарантируется, что любые две модели снегоуборщиков различаются по мощности или по стоимости. Закупить подходящий набор снегоуборщиков всегда можно.
Входные данные
В первой строке входного файл INPUT.TXT заданы два натуральных числа N и К. В следующей строке записано N натуральных чисел Wi через пробел. Далее в K строках записано по два натуральных числа Pj и Cj. (1 ≤ N ≤ 2×105; 1 ≤ Cj ≤ 106; 1 ≤ K, Pj, Wi ≤ 105).
Выходные данные
В выходной файл OUTPUT.TXT выведите два натуральных числа: сначала суммарную стоимость всех купленных снегоуборщиков, затем максимальную мощность среди них.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3 4
1 2 3
10 7
1 5
3 7
2 3 | 13 10 |
Автор задачи
Владимир Игоревич Лукьянчиков
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
