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