Задание 26 из ЕГЭ по информатике: задача 3

Для дачных участков СНТ необходимо закупить снегоуборщики. Для каждого из N участков будет куплен свой снегоуборщик. Известны минимальные требования к мощности этой техники для каждого из участков. Для закупки доступно K моделей снегоуборщиков определённой мощности и стоимости. Количество экземпляров каждой модели не ограничено.

Для каждого участка выбирается снегоуборщик минимальной стоимости, мощность которого не меньше требуемой; при одинаковой стоимости выбирается модель максимальной мощности.

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

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

Первая строка входного файла содержит два натуральных числа: N (1 < N < 1 000 000) — количество участков СНТ и K (1 < K < 100 000) — количество моделей снегоуборщиков. Следующие N строк содержат по одному натуральному числу, не превышающему 1000, — минимальные требования к мощности для каждого участка. Далее в каждой из K строк содержится пара натуральных чисел — мощность модели и её стоимость. Мощность не превосходит 1000, стоимость — 100 000.

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

Два числа: суммарная стоимость всех купленных снегоуборщиков и максимальная мощность среди них.

Типовой пример:

3 4
1
2
3
10 7
1 5
3 7
2 3

Для первого и второго участков выбирается снегоуборщик мощностью 2 стоимостью 3, для третьего — мощностью 10. Ответ: 13 10.