Задача #2168

(Л. Шастин) Известно расписание движения автобусов одного из районов некоторого густонаселенного города за 2023 год, составленное с опорой на то, что в любом месяце ровно 30 дней. Транспортные логисты называют "прайм-таймом" такой отрезок времени, в каждую минуту которого работают хотя бы K автобусов, но при этом в минуту до начала отрезка и в минуту после конца отрезка работает меньше K автобусов. Причём считается, что в первую минуту (в точке начала отрезка) и в последнюю минуту (в точке конца отрезка) автобус все ещё работает. Специалисты владеют данными об отрезках времени, задающих время начала и конца непрерывной работы соответствующего автобуса. Данные о времени представлены в формате D.M.H.T (минута T часа H дня D месяца M). По имеющимся данным определите количество "прайм-таймов", а также наибольшее число автобусов, работавших одновременно в какую-либо минуту.

Примечание. Например, запись 20.03.16.57 отождествляет дату и время: 20 марта, 16:57.

Входные данные

В первой строке входного файла находится число N – количество автобусов в текущем расписании (натуральное число, не превышающее 10 000), а во второй строке число K – минимальное количество автобусов, которые должны работать во время "прайм-тайма". В каждой из следующих N строк находятся два строковых значения, которые задают время начала и время конца работы соответствующего автобуса в формате D.M.H.T, причём все значения отделены друг от друга пробельным знаком.

Запишите в ответе два числа: сначала количество "прайм-таймов", а затем наибольшее число автобусов, работавших одновременно в какую-либо минуту.

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

5
2
14.04.17.31 30.10.19.31
03.03.09.18 07.03.22.15
01.01.00.00 27.05.18.25
23.09.17.46 30.12.23.57
21.08.15.11 30.12.21.18

При таких исходных данных число "прайм-таймов" равно трём, и при этом максимум три автобуса (№1, 2 и 3) работали одновременно.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.