Задача #1731

(Л. Шастин) Входной файл содержит заявки пассажиров, желающих сдать свой багаж в камеру хранения. В заявке указаны вес, время сдачи багажа и время освобождения ячейки (в минутах от начала суток). Багаж одного пассажира размещается в одной свободной и подходящей по вместимости для хранения багажа ячейке с минимальным номером (это правило работает для всех пассажиров, кроме того, который сдаст свой багаж последним – он может выбрать любую свободную ячейку, в которую вмещается его багаж). Ячейки пронумерованы, начиная с единицы. Размещение багажа в ячейке или её освобождение происходит в течение 1 минуты. Багаж можно поместить в только что освобождённую ячейку, начиная со следующей минуты. Если в момент сдачи багажа свободных и подходящих ячеек нет, то пассажир уходит. Среди одновременно пришедших первыми обслуживаются пассажиры с меньшим весом багажа и, если вес одинаковый, с самым ранним временем освобождения ячейки. Определите, сколько пассажиров сможет сдать свой багаж в течение 24 часов и какой номер будет иметь ячейка, которую займут последней. Если таких ячеек может быть несколько, укажите максимально возможный номер ячейки.

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

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