Задание выполняется с использованием прилагаемых файлов.
В магазине представлено K различных моделей солнечных панелей. Каждая модель доступна к покупке в неограниченном количестве панелей размером 1 на 1 (в метрах).
Фермер решил обеспечить электроэнергией свои N теплиц, установив солнечные панели. Для каждой теплицы требуется определенная минимальная суммарная мощность солнечных панелей. Для каждой теплицы необходимо приобрести солнечные панели только одного вида так, чтобы их суммарная мощность была не меньше минимальной требуемой мощности для данной теплицы, а суммарная стоимость этих панелей была минимально возможной. Определите минимальную сумму, которую фермер потратит на покупку солнечных панелей для всех теплиц, а также сумму мощностей всех купленных панелей в этом случае. Гарантируется, что для всех теплиц можно подобрать искомый набор солнечных панелей.
Входные данные
В первой строке входного файла находятся два числа: N – количество теплиц (натуральное число, не превышающее 100 000) и число K – количество моделей солнечных панелей (натуральное число, не превышающее 100 000). В следующих N строках находятся минимальные значения суммарной мощности для каждой теплицы, а также длина и ширина её крыши в метрах (все числа натуральные, не превышающие 1 000 000).
В последних K строках указаны два натуральных числа, не превышающих 1 000 000, для каждой модели солнечной панели: стоимость и мощность одной модели. Гарантируется, что любые две модели имеют либо разную стоимость одной панели, либо разную мощность.
Запишите в ответе два целых числа: сначала сумму, которую потратят на покупку солнечных панелей для всех теплиц, затем сумму мощностей всех купленных панелей.
Типовой пример организации данных во входном файле:
3 3
70 2 3
40 5 4
60 2 6
36 30
89 30
34 90
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.