eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Перукар

Перукар

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Тато Петі працює перукарем. Його перукарня зовсім невеличка, він — єдиний перукар, який у ній працює. Перукарня відчиняється о 9:00 і зачиняється о 17:00, але тато залишається на роботі, доки не обслугує усіх клієнтів, які зайшли до перукарні до 17:00.

Обслуговування у перукарні відбувається наступним чином. Коли черговий клієнт заходить до перукарні і перукар вільний, то він негайно розпочинає стригтись. У протилежному випадку клієнт чекає, доки закінчиться стрижка усіх клієнтів, які зайшли у перукарню до нього. Протягом дня кожен момент часу, коли до перукарні заходить черговий клієнт, записується у журналі реєстрації. Також у журналі реєстрації записується час, коли останній клієнт залишіє перукарню. Щоб оптимізувати свою роботу, перукар хоче визначити, скільки може продовжуватись сама тривала стрижка. На жаль, за вказаними записами не завжди можна визначити це точно. Тому для початку перукар хоче визначити граничний час стрижки, а саме, який мінімальний час могла продовжуватись найдовша стрижка. Відомо також, что довільна стрижка займає не менше п'яти хвилин. Потрібно написати програму, яка за інформацією про моменти входу до перукарні усіх клієнтів, а також моменту завершення стрижки останнього клієнта, визначає, який мінімальний час могла тривати найдовша стрижка.

Вхідні дані

Перший рядок вхідного файлу містить число N — кількість клієнтів, обслужених у розглядуваний день (1N50). Наступні 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 хвилин очевидний.

У останньому прикладі клієнта було обслужено за одну хвилину, чого не може бути за умовою задачі.

Приклад

Вхідні дані #1
2
09:00
16:22
17:52
Вихідні дані #1
90.0