Покупка снегоуборщиков
Для дачных участков нужно закупить снегоуборщики: для каждого из участков будет куплен свой снегоуборщик. Для каждого участка известна минимальная необходимая мощность. Для закупки доступно моделей снегоуборщиков, у каждой модели своя мощность и стоимость; количество экземпляров каждой модели не ограничено.
Для каждого участка выбирают снегоуборщик минимальной стоимости, мощность которого не меньше требуемой; при одинаковой стоимости выбирают модель максимальной мощности. Определите общую стоимость закупки и максимальную мощность снегоуборщика среди купленных.
Входные данные
В первой строке находятся два натуральных числа: — количество участков () и — количество моделей (). В каждой из следующих строк находится минимальная необходимая мощность для одного участка — натуральное число, не превышающее 1000. Далее каждая из строк содержит два натуральных числа: мощность очередной модели (не превышает 1000) и её стоимость (не превышает ).
Модели идут в произвольном порядке. Гарантируется, что любые две модели различаются мощностью или стоимостью и что для каждого участка есть подходящая модель.
Выходные данные
Выведите два целых числа: сначала общую стоимость всех купленных снегоуборщиков, затем максимальную мощность среди них.
Примеры
3 4 1 2 3 10 7 1 5 3 7 2 3
13 10
2 2 1000 1000 999 1 1000 100000
200000 1000
Примечание
В первом примере для первых двух участков покупают модель мощностью 2 за 3, а для третьего — модель мощностью 10 за 7. При одинаковой цене 7 она предпочтительнее модели мощностью 3. Общая стоимость равна 13. Во втором примере для обоих участков подходит только модель мощностью 1000.