Задание №26

Входной файл содержит заявки пассажиров, желающих сдать свой багаж в камеру хранения, состоящей из множества ячеек. Для каждой ячейки известна стоимость хранения одного багажа.

В заявке указано время сдачи багажа (в минутах от начала суток) и время хранения багажа в ячейке. Багаж каждого пассажира занимает ровно одну ячейку и может поместиться в любую ячейку. Если в момент сдачи багажа свободных ячеек нет, пассажир уходит. Если свободных ячеек несколько, пассажир выбирает свободную ячейку с наименьшей стоимостью, а среди ячеек с одинаковой стоимостью — ячейку с наименьшим номером. Размещение багажа в ячейке или её освобождение происходит моментально, после освобождения следующей ячейки пассажир может сразу же занять эту ячейку.

Определите сумму, которая потребуется для хранения багажа тех пассажиров, которые смогут оставить свой багаж в течение 18 ч (от начала суток), а также номер ячейки, в которую будет размещён последний сданный багаж за 18 ч.

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

Каждая из последующих K строк содержит два натуральных числа, не превышающих 1440: указанное в заявке время размещения багажа в ячейке (в минутах от начала суток) и срок хранения багажа (в минутах). Гарантируется, что время размещения багажа любых двух пассажиров различно).

Запишите в ответе два целых числа: сначала общую стоимость хранения сданных за 18 ч багажей, затем номер ячейки последнего сданного багажа за 18 ч.

Типовой пример организации данных во входном файле
2 5
70
60
30 30
40 960
59 1
61 939
1010 430

Пример организации данных приведён для двух ячеек и пяти пассажиров.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.