Для районов города необходимо закупить снегоуборщики. Для каждого из N районов будет куплен свой снегоуборщик. Известны минимальные требования к мощности этой техники для каждого из районов.
Для закупки доступно К моделей снегоуборщиков определённой мощности и стоимости. Количество экземпляров каждой модели не ограничено. Для каждого района выбирается снегоуборщик минимальной стоимости, мощность которого не меньше требуемой; при одной и той же стоимости выбирается модель максимальной мощности.
Требуется определить общую стоимость закупки и максимальную мощность снегоуборщика, входящего в число купленных. В ответе запишите два числа: сначала суммарную стоимость всех купленных снегоуборщиков, затем максимальную мощность среди них.
Входныеданные
Первая строка входного файла содержит два натуральных числа: N (1 < N < 1 000 000) - количество районов города и К (1 < K < 100 000) - количество моделей снегоуборщиков соответственно.
Следующие N строк содержат по одному натуральному числу, не превышающему 1000, минимальные мощности снегоуборщиков, которые можно закупить для каждого из N районов. Далее в каждой из К строк содержится пара натуральных чисел - мощность очередной модели снегоуборщика и её стоимость соответственно. Мощность снегоуборщиков не превосходит 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.
