Петин папа работает парикмахером. Его парикмахерская совсем
небольшая, он — единственный парикмахер, который в ней работает. Парикмахерская
открывается в 9:00 и закрывается в 17:00, но папа остаётся на работе, пока не
обслужит всех клиентов, которые зашли в парикмахерскую до 17:00.
Обслуживание в парикмахерской происходит следующим образом.
Когда очередной клиент заходит в парикмахерскую и парикмахер свободен, то он
немедленно начинает стричься. В противном случае клиент ждёт, пока закончится
стрижка всех клиентов, которые вошли в парикмахерскую до него.
В течение дня каждый момент времени, когда в парикмахерскую
заходит очередной клиент, записывается в журнале регистрации. Также в журнале
регистрации записывается время, когда последний клиент покидает парикмахерскую.
Чтобы оптимизировать вою работу, парикмахер хочет определить, сколько может
продолжаться самая долгая стрижка. К сожалению, по указанным записям не всегда
можно определить это точно. Поэтому для начала парикмахер хочет определить
предельное время стрижки, а именно, какое минимальное время могла продолжаться самая
долгая стрижка. Известно также, что любая стрижка занимает не менее пяти минут.
Требуется написать программу, которая по информации о
моментах входа в парикмахерскую всех клиентов, а также моменту окончания
стрижки последнего клиента, определяет, какое минимальное время могла
продолжаться самая долгая стрижка.
Формат входных данных
Первая строка входного файла содержит число n —
количество клиентов, обслуженных в рассматриваемый день (1 <= n <= 50).
Следующие n строк содержат моменты времени входа клиентов в
парикмахерскую в формате hh:mm. Времена заданы в порядке входа клиентов в
парикмахерскую и находятся в диапазоне от 09:00 до 17:00. Последняя строка
содержит время выхода из парикмахерской последнего клиента также в формате
hh:mm. Это время находится в диапазоне от 09:00 до 18:59.
Формат выходных данных
Выведите в выходной файл минимальное возможное время самой
долгой стрижки в минутах. Ответ должен отличаться от правильного не более чем
на 10-8. Если парикмахер не может обслужить клиентов за указанное
время, выведите "-1".
Примеры входных и выходных файлов
|
stdin
|
stdout
|
|
2
09:00
16:22
17:52
|
90.0
|
|
3
09:00
09:22
09:22
10:11
|
23.666666666667
|
|
1
16:59
17:00
|
-1
|
Пояснения к примерам
Покажем, что в первом примере максимальное время стрижки не
может быть меньше 90 минут от противного. Пусть любая стрижка продолжалась
меньше 90 минут. Известно, что стрижка второго клиента завершилась в 17:52.
Поскольку она продолжалась меньше 90 минут, то она началась позже, чем в 16:22.
Значит, обслуживание второго клиента началось не сразу, как он пришёл, а после
того, как закончилась стрижка первого клиента после 16:22. Но тогда первого
клиента стригли больше 7 часов. А мы предполагали, что максимальное время
стрижки меньше 90 минут. Пришли к противоречию. А расписание для 90 минут
очевидно.
В последнем примере клиент был обслужен за одну минуту, чего
не может быть по условию задачи.
