eolymp
bolt
Try our new interface for solving problems
Məsələlər

Бронирование

Бронирование

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

У Пьера сегодня большие проблемы! Он отвечает за управление бронирования номеров для РУЦ (Размещение по Умеренной Цене) отеля и буквально недавно понял, что программное обеспечение бронирования содержит серьезный баг. Это создало прецендент перекрывания и неправильного назначения номеров. Пьер очень обеспокоен тем, что отель может быть перебронирован. Поскольку производитель программного обеспечения не является ни отзывчивым, ни компетентным человеком, то Пьер должен делать все сам, своевременно принимая контрмеры в случае необходимости.

К счастью, Пьер был в состоянии экспортировать все оригинальные заказы (в том числе коды бронирования и действительные даты заезда и выезда). Единственная информация, которая потерялась - это время бронирования, так что Пьер не знает приоритетов бронирования (первой заказана - первой обслужена). Используя имеющуюся информацию, не могли бы вы помочь Пьеру и сообщить ему распределение номеров используя минимальное количество комнат так, чтобы удовлетворить все заказы? Обратите внимание на то, что номер должен всегда быть убран перед повторным использованием. Так как Пьер не хочет рисковать, он просит Вас рассматривать только максимальное время уборки.

Giriş verilənləri

Первая строка содержит количество t (1t100) тестов. Первая строка каждого теста содержит два целых числа: количество бронирований b (1b5000) и время уборки c (0c360) (в минутах) для одной комнаты. Каждая из следующих b строк содержит код резервации (произвольная строка из букв и цифр до 20 символов) и даты прибытия и выезда для одного бронирования. Даты заданы в формате "YYYY-MM-DD HH:MM" (как указано в примере), годы резервирования варьируются от 2013 до 2016.

Çıxış verilənləri

Для каждого теста выведите в отдельной строке минимальное количество необходимых номеров. Помните о високосных годах, но игнорируйтре Летнее время.

Nümunə

Giriş verilənləri #1
4
2 120
1 2013-07-01 15:59 2013-07-08 16:30
2 2013-07-08 17:30 2013-07-15 12:00
3 60
65 2013-07-08 14:30 2013-07-08 16:00
32 2013-07-01 16:00 2013-07-15 12:00
91 2013-07-01 16:00 2013-07-08 15:00
2 360
a7 2016-02-21 14:00 2016-02-28 21:00
xx 2016-03-01 01:00 2016-03-02 12:57
2 60
a9 2016-02-21 14:00 2016-02-28 11:00
a8 2016-02-28 12:00 2016-03-11 21:00
Çıxış verilənləri #1
2
3
1
1
Mənbə 2013 German Collegiate Programming Contest, Задача B