Задание выполняется с использованием прилагаемых файлов.
В одном из населённых пунктов есть N дачных участков, для которых необходимо приобрести газонокосилки. В магазине есть K видов газонокосилок, каждая с определённой мощностью и стоимостью. Для каждого участка необходимо приобрести одну газонокосилку так, чтобы её мощность была не меньше, чем минимальная необходимая мощность для участка. Если таких газонокосилок несколько, необходимо приобрести газонокосилку с наименьшей стоимостью. Если есть несколько подходящих газонокосилок с наименьшей стоимостью, для участка приобретают газонокосилку с максимальной мощностью. Количество косилок каждого вида не ограничено.
Определите сумму, которую потратят на покупку газонокосилок с наибольшей мощностью (учитывая только купленные), а также количество различных видов газонокосилок, которое потребуется приобрести в этом случае.
Гарантируется, что для всех участков можно подобрать искомый набор газонокосилок.
Входные данные
В первой строке входного файла находятся два числа: N – количество участков (натуральное число, не превышающее 1 000 000) и число K – количество видов газонокосилок в магазине (натуральное число, не превышающее 100 000). В следующих N строках находятся минимальные значения мощности газонокосилки для каждого участка (все числа натуральные, не превышающие 1000). В последних K строках указаны два числа: мощность газонокосилки (натуральное число, не превышающее 1000) и стоимость одной газонокосилки. Гарантируется, что любые два вида газонокосилок имеют либо разную стоимость одной газонокосилки, либо разную мощность.
Запишите в ответе два целых числа: сначала сумму, которую потратят на покупку газонокосилок наибольшей мощности, затем количество различных видов купленных газонокосилок.
Типовой пример организации данных во входном файле
3 3
1
3
2
10 7
3 7
2 1
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.