26_0237

Для дачных участков СНТ необходимо закупить снегоуборщики. Для каждого из $N$ участков будет куплен свой снегоуборщик. Известны минимальные требования к мощности этой техники для каждого из участков. Для закупки доступно $K$ моделей снегоуборщиков определённой мощности и стоимости. Количество экземпляров каждой модели не ограничено. Для каждого участка выбирается снегоуборщик минимальной стоимости, мощность которого не меньше требуемой; при одной и той же стоимости выбирается модель максимальной мощности. Требуется определить общую стоимость закупки и максимальную мощность снегоуборщика, входящего в число купленных.

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

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

Первая строка входного файла содержит два натуральных числа: $N$ ($1 < N < 1\thinspace 000\thinspace 000$) - количество участков СНТ и $K$ ($1 < K < 100\thinspace 000$) - количество моделей снегоуборщиков соответственно. Следующие $N$ строк содержат по одному натуральному числу, не превышающему 1000, минимальные мощности снегоуборщиков, которые можно закупить для каждого из $N$ участков. Далее в каждой из $K$ строк содержится пара натуральных чисел - мощность очередной модели снегоуборщика и её стоимость соответственно. Мощность снегоуборщиков не превосходит 1000, стоимость - 100 000. Гарантируется, что любые две модели снегоуборщиков различаются по мощности или по стоимости. Закупить подходящий набор снегоуборщиков всегда можно.

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

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

Типовой пример организации данных во входном файле

3 4
1
2
3
10 7
1 5
3 7
2 3

При таких исходных данных для первого и второго участков оптимально закупить одинаковые снегоуборщики мощностью 2 и стоимостью 3, для третьего участка будет закуплен снегоуборщик мощностью 10. Стоимость закупки составит 3 + 3 + 7 = 13. Ответ: 13; 10.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Файлы к заданию:

• 26_0237.txt