Олимпиадный тренинг

Задача . ТР03. Задание 26. Выбор по стоимости и мощности


Задание выполняется с использованием прилагаемых файлов.

В одном из населённых пунктов есть 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. Пример имеет иллюстративный характер; для выполнения задания используйте данные прилагаемого файла.

Запись ответа на платформе. Введите два числа в указанном в условии порядке, разделив их одним пробелом.