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