Задача #3999

(Даня Байт) Для предприятий промышленной зоны необходимо закупить генераторы. Для каждого из N предприятий будет куплен свой генератор. Известны минимальные требования к мощности генератора для каждого предприятия. Для закупки доступно K моделей генераторов определённой мощности и стоимости. Количество экземпляров каждой модели не ограничено.

Для каждого предприятия выбирается генератор минимальной стоимости, мощность которого не меньше требуемой; при одной и той же стоимости выбирается модель максимальной мощности.

Требуется определить:

• общую стоимость закупки,
  
  

• и максимальную мощность генератора, входящего в число купленных.
  
  

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

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

Первая строка входного файла содержит два натуральных числа:
N(1 < N < 1 000 000) — количество предприятий, и K (1 < K < 100 000) — количество моделей генераторов. Следующие N строк содержат по одному натуральному числу, не превышающему 1000 — минимальные мощности генераторов, которые необходимо установить на каждом предприятии.

Далее в каждой из K строк содержится пара натуральных чисел — мощность очередной модели генератора и её стоимость соответственно.

Мощность генераторов не превосходит 1000, стоимость — 100 000. Гарантируется, что любые две модели генераторов различаются по мощности или по стоимости. Закупить подходящий набор генераторов всегда можно.