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