Задание выполняется с использованием прилагаемых файлов.
Для дачных участков СНТ необходимо закупить снегоуборщики. Для каждого из N участков будет куплен свой снегоуборщик. Известны требуемые мощности этой техники для каждого из участков.
Для закупки доступно K моделей снегоуборщиков определённой мощности и стоимости (стоимость представлена для трёх разных магазинов). Количество экземпляров каждой модели не ограничено. Для каждого участка выбирается снегоуборщик, мощность которого соответствует требуемой. Если для участка не находится подходящей модели, то участок не учитывается в закупке. Требуется определить минимально возможную общую стоимость закупки и количество уникальных купленных снегоуборщиков.
Входные данные
Первая строка входного файла содержит два натуральных числа: N (\(1 \le N \le 1\,000\,000\)) — количество участков в СНТ и K (\(1 \le K \le 1\,000\,000\)) — количество моделей снегоуборщиков соответственно.
Следующие K строк содержат по четыре натуральных числа, не превышающих 10 000: мощность очередной модели снегоуборщика и его стоимости в трёх различных магазинах. Гарантируется, что у любых снегоуборщиков одинаковой мощности их стоимости во всех магазинах различны.
Далее в каждой из N строк содержится пара натуральных чисел — необходимая мощность снегоуборщика для каждого из N участков и максимальная возможная стоимость для закупки. Все числа не превышают 10 000.
Запишите в ответе два целых числа: сначала суммарную стоимость всех купленных снегоуборщиков, затем количество уникальных снегоуборщиков из них.
Типовой пример организации данных во входном файле:
3 4
40 160 140 170
20 90 110 80
50 250 200 290
40 130
50 200
20 100
50 150
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.