№26 — #2615

Для дачных участков СНТ необходимо закупить снегоуборщики. Для каждого из 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. Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.