Задача 17 из 21

Покупка снегоуборщиков

Время 2 с · память 256 МБ

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

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

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

В первой строке находятся два натуральных числа: NN — количество участков (1<N≤100 0001 < N \le 100\,000) и KK — количество моделей (1<K<100 0001 < K < 100\,000). В каждой из следующих NN строк находится минимальная необходимая мощность для одного участка — натуральное число, не превышающее 1000. Далее каждая из KK строк содержит два натуральных числа: мощность очередной модели (не превышает 1000) и её стоимость (не превышает 100 000100\,000).

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

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

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

Примеры

Ввод 1
3 4
1
2
3
10 7
1 5
3 7
2 3
Вывод 1
13 10
Ввод 2
2 2
1000
1000
999 1
1000 100000
Вывод 2
200000 1000

Примечание

В первом примере для первых двух участков покупают модель мощностью 2 за 3, а для третьего — модель мощностью 10 за 7. При одинаковой цене 7 она предпочтительнее модели мощностью 3. Общая стоимость равна 13. Во втором примере для обоих участков подходит только модель мощностью 1000.

Решение
Загрузка редактора…
Результат появится здесь

Черновик сохраняется в этом браузере.

Ошибка в задаче