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

(Д. Бахтиев) Николай устроился работать гардеробщиком в крупнейший кинотеатр города. Всего в гардеробе доступно N мест. При покупке билетов на какой-либо сеанс, они резервируются на уникальный ID клиента, причём на один ID может быть зарегистрировано сразу несколько билетов. Каждый посетитель кинотеатра обязан сдать одежду в гардероб, при этом взаимодействовать с Николаем может только клиент, ID которого использован для покупки билетов. Если посетитель подходит к гардеробу впервые, он сдаёт одежду за себя и всю свою группу и получает столько номерков, за сколько человек одежда была сдана. При повторном визите посетитель забирает свою одежду и одежду своей группы, и номерки становятся свободными. Считается, что одежда развешивается и выдаётся моментально, то есть, если клиент подошёл в минуту t для получения одежды, то в минуту t этой одежды в гардеробе уже нет. Если несколько посетителей подошли в одно время, то они обслуживаются в порядке возрастания их ID. Если свободных номерков нет или их меньше, чем количество человек, которые хотят сдать одежду, то им отказывается в обслуживании, на что каждый клиент группы один раз злобно топает ножкой и моментально покидает кинотеатр, второй раз при этом они подходить не будут. Определите и запишите в ответе сначала сколько клиентов за сутки недовольно топнут ножкой, а затем суммарную продолжительность времени, в течение которого в гардеробе были заняты все места.

Примечание: считается, что в момент открытия кинотеатра все места в гардеробе свободны.

Входные данные: В первой строке входного файла записаны два числа N и K: N — общее количество мест в гардеробе; K — количество людей, на чьё имя были куплены билеты в кинотеатр.

Далее следуют строки с информацией о посетителях кинотеатра за последние сутки. Каждая строка содержит три числа, разделённых пробелами: ID — уникальный идентификатор клиента; t — время подхода клиента к гардеробу в минутах от начала суток; M — количество билетов, оформленных на текущий ID.

Гарантируется, что каждый идентификатор ID появляется в данных не более двух раз: первый раз — для сдачи одежды, второй раз — для её получения.

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

5 3 20 15 4 4 5 2 1996 28 3 1996 34 3 20 40 4 4 50 2 Пример входного файла приведён для гардероба, имеющего 5 мест, и трёх клиентов. При таких исходных данных клиент с ID= 4 получит 2 номерка, клиент с ID= 20 не сможет разместить вещи в гардеробе, поэтому 4 посетителя топнут ножкой; клиент с ID=1996 получит 3 номерка и все 5 номерков гардероба в момент времени t = 28 будут заняты до тех пор, пока этот же клиент при t = 34 не заберёт вещи. Ответ: 4 6.