Задание 26 ЕГЭ по информатике

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

Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18967_26.txt