Петин папа работает парикмахером. Его парикмахерская совсем не большая, и он — единственный парикмахер, который в ней работает. Парикмахерская открывается в 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».
Примеры входных и выходных файлов
| входные данные |
выходные данные |
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 |
Пояснения к примерам
В первом примере, чтобы второму клиенту пришлось ждать времени окончания стрижки первого, тот должен был бы стричься более 7 часов. Второй же клиент освободился через 90 минут после того, как вошел в парикмахерскую, значит, самая долгая стрижка займет не менее 90 минут.
Во втором примере два клиента, которые зашли в 9:22, были суммарно обслужены за 49 минут. Они вошли через 22 минуты после первого клиента. Самая долгая стрижка в этом случае займет не менее 23 2/3 минут. Данная оценка достигается тогда, когда обслуживание всех трех клиентов продолжалось одно и то же время.
В последнем примере клиент был обслужен за одну минуту, чего не может быть по условию задачи.