Обработка данных с сортировкой

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

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

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

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

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

2

2 7

1010 1 2 440 2 1 890 2 1 310 1 2 170 2 2 540 1 2 1390 2 1

При таких исходных данных билеты без изменений будут утверждены по заявкам №2, 4 и 5. Последний утвержденный билет по заявке №6 будет не соответствовать заявке (он будет определен на место №1 в вагоне №1, т.к. место №2 в вагоне №1 уже занято). Ответ: 1 2.

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