Задача #1060

(В. Рыбальченко)Рядом с жилым домом есть платная парковка, состоящая из трех уровней. На каждом уровне по К парковочных мест. Стоимость парковки за час на первом уровне равна С, на втором 2С, на третьем 4С. За день на парковку приезжает N машин (гарантируется, что все машины приехали в разное время). Записи, когда приехал клиент идут в случайном порядке. Водитель выбирает один из трех уровней, покупает целое количество часов и занимает первое свободное место в тот же момент, как приехал. Место считается свободным через минуту, после того как водитель планировал уехать. Если все места заняты – клиент уезжает. Необходимо определить сколько владелец парковки заработает за день и сколько клиентов получится обслужить.

Входные данные
На первой строке одно число N – количество клиентов, приехавших за день. На второй строке одно число K – количество парковочных мест на каждом уровне. На третье строке одно число С – стоимость парковки на первом уровне. Далее N строк, в каждой из которых указано время, когда клиент приехал, время, когда он планирует уехать (дано в секундах от начала дня) и уровень парковки, который водитель хочет выбрать.

Типовой пример организации данных:
6
1
10
10 3600 1
1500 3600 2
3650 7100 1
8100 8200 3
3660 9000 2
4000 5000 1
При таких данных встать на парковку смогут первый, второй, четвертый, пятый и шестой клиенты. Ответ 120 5