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