Задача #1582

(Л. Шастин) Гостевой зал одного из ресторанов города включает в себя K столиков, которые сохранены в базе данных по номерам от 1 до К.

В call-центр ресторана звонят клиенты, желая забронировать столик. В отчете предоставлена информация о звонках, которые происходили за вчерашний день. Известно время, на которое каждый клиент хочет забронировать столик на сегодняшний день, ID-номер конкретного столика, им выбранного, и время, в которое был совершен текущий звонок. При этом, согласно регламенту ресторана, любой столик бронируется ровно на 120 минут. Администратор выделяет для клиента столик, если на то время, в которое клиент желает пребывать в ресторане, не назначено другой, ранее сделанной брони. Но если тот столик, который хочет забронировать клиент, уже занят, тогда администратор выделяет для клиента другой столик с наименьшим ID-номером, среди всех тех, что свободны в рассматриваемое время. Каждый столик считается свободным со следующей минуты после окончания предыдущей брони, время на его уборку не входит в учёт. Если свободных столиков нет, то администратор просит прощения у клиента и сообщает, что он не может записать его.

Длительность рабочего дня ресторана составляет 1440 минут. Последняя минута возможной брони столика = 1320.

Определите, сколько клиентов смогли забронировать столик, а также номер столика, который был выделен для предпоследнего клиента.

Входные данные

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

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

Типовой пример организации данных во входном файле

5
2
130 2 20
150 2 10
570 1 300
180 2 50
600 1 200

При таких исходных данных первый, второй, третий и пятый клиенты смогут забронировать столик. Предпоследним будет забронирован столик с номером 1.

Ответ для примера: 4 1.

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