Задание выполняется с использованием прилагаемых файлов.
Входной файл содержит заявки пассажиров, желающих сдать свой багаж в камеру хранения. В заявке указаны время сдачи багажа и время хранения багажа в ячейке (в минутах от начала суток). Багаж одного пассажира размещается в одной свободной ячейке с минимальной стоимостью хранения.
Если ячеек с наименьшей стоимостью хранения несколько, багаж размещается в ячейке с максимальным номером такой ячейки. Ячейки пронумерованы начиная с единицы. Размещение багажа в ячейке или её освобождение происходит в течение 1 мин. Багаж можно поместить в только что освобождённую ячейку начиная со следующей минуты. Если в момент сдачи багажа свободных ячеек в подходящем ценовом сегменте нет, то пассажир уходит. Определите, какую сумму (в руб.) заплатят все пассажиры, которые смогут воспользоваться камерой хранения, и какой номер будет иметь ячейка, которую займут последней.
Входные данные
В первой строке входного файла находятся два числа: N – количество ячеек (натуральное число, не превышающее 1 000 000) и число K – количество пассажиров (натуральное число, не превышающее 100 000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 10 000: стоимость хранения багажа в ячейке. Стоимость хранения указана в порядке нумерации ячеек, начиная с первой. Каждая из последующих K строк содержит два натуральных числа, не превышающих 1440: указанное в заявке время размещения багажа в ячейке (в минутах от начала суток) и срок хранения багажа (в минутах).
Запишите в ответе два целых числа: сначала сумму (руб.), которую заплатят все пассажиры, воспользовавшиеся камерой хранения, и номер последней занятой ячейки.
Типовой пример организации данных во входном файле
5 2
70
60
30 30
40 960
59 1
61 939
1010 430
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.