Задача #2726

(Д. Бахтиев) Николай устроился работать гардеробщиком в крупнейший кинотеатр города. Всего в гардеробе доступно $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$.