Парикмахер
Петин папа работает парикмахером. Его парикмахерская совсем небольшая, он — единственный парикмахер, который в ней работает. Парикмахерская открывается в 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.
Примечания
Покажем, что в первом примере максимальное время стрижки не может быть меньше 90 минут. Положим противное: пусть любая стрижка продолжалась меньше 90 минут. Известно, что стрижка второго клиента завершилась в 17:52. Поскольку она продолжалась меньше 90 минут, то она началась позже, чем в 16:22. Значит, обслуживание второго клиента началось не сразу, как он пришёл, а после того, как закончилась стрижка первого клиента после 16:22. Но тогда первого клиента стригли больше 7 часов. А мы предполагали, что максимальное время стрижки меньше 90 минут. Пришли к противоречию. А расписание для 90 минут очевидно.
В последнем примере клиент был обслужен за одну минуту, чего не может быть по условию задачи.