Задание №42271 ЕГЭ по Информатике

Для дачных участков СНТ необходимо закупить снегоуборщики. Для каждого из N участков будет куплен свой снегоуборщик. Известны минимальные требования к мощности этой техники для каждого из участков. Для закупки доступно K моделей снегоуборщиков определённой мощности и стоимости. Количество экземпляров каждой модели не ограничено. Для каждого участка выбирается снегоуборщик минимальной стоимости, мощность которого не меньше требуемой; при одной и той же стоимости выбирается модель максимальной мощности. Требуется определить общую стоимость закупки и максимальную мощность снегоуборщика, входящего в число купленных. В ответе запишите два числа: сначала суммарную стоимость всех купленных снегоуборщиков, затем максимальную мощность среди них. Входные данные Первая строка входного файла содержит два натуральных числа: N (1 < N < 1 000 000) — количество участков СНТ и K (1 < K < 100 000) — количество моделей снегоуборщиков соответственно. Следующие N строк содержат по одному натуральному числу, не превышающему 1000, — минимальные мощности снегоуборщиков, которые можно закупить для каждого из N участков. Далее в каждой из K строк содержится пара натуральных чисел — мощность очередной модели снегоуборщика и её стоимость соответственно. Мощность снегоуборщиков не превосходит 1000, стоимость — 100 000. Гарантируется, что любые две модели снегоуборщиков различаются по мощности или по стоимости. Закупить подходящий набор снегоуборщиков всегда можно. Выходные данные В ответе укажите два искомых числа: суммарную стоимость всех купленных снегоуборщиков и максимальную мощность среди них. Типовой пример организации данных во входном файле
3 4
1
2
3
10 7
1 5
3 7
2 3
При таких исходных данных для первого и второго участков оптимально закупить одинаковые снегоуборщики мощностью 2 и стоимостью 3, для третьего участка будет закуплен снегоуборщик мощностью 10. Стоимость закупки составит 3 + 3 + 7 = 13. Ответ: 13; 10. Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.