Задача #2145

(Л. Шастин) Скоростной поезд, направляющийся из Москвы в Санкт-Петербург, ожидает пассажиров. Состав поезда включает в себя K сцепленных пассажирских вагонов, каждый из которых содержит M пассажирских мест. Вагоны и места в них нумеруются от 1 до K и от 1 до M соответственно. Известен перечень, состоящий из N заявок на бронь билетов на поезд за вчерашний день. В каждой из заявок указано время подачи заявки (в минутах от начала суток) и желаемый номер вагона и номер места в нём. Оператор обрабатывает заявки последовательно, начиная с ранее поданных (среди заявок, поданных в одинаковое время, прежде обрабатываются заявки с наименьшими указанными в них номерами вагонов и, если номера вагонов совпали, с наименьшими номерами мест в этих вагонах), и если указанное в заявке место в нужном вагоне ещё свободно, утверждает билет на это место, а иначе утверждает билет на наименьшее по номеру свободное место, расположенное в вагоне, который находится как можно ближе к кабине машиниста (вагон с кабиной машиниста имеет нулевой номер и не является пассажирским). Если же свободных мест нет, билет не утверждается. Определите количество пассажиров, которые получили билет в несоответствии со своей заявкой, а также сумму номеров вагона и места в последнем утвержденном билете.