Remote Training on Programming

Наверное, все согласятся, что наша почта всегда могла служить эталоном сервиса и качества услуг. Однако, в удалённых уголках нашей страны, возможно, ещё встречаются отдельные недостатки. Например, никогда не знаешь, сколько простоишь в очереди, получая посылку. Не знает этого и Сигизмунд − единственный посетитель почтового отделения в деревне Васюки. Как и подобает современному человеку, он заказывает через Интернет всякую всячину, которую потом получает на почте.

Почтовое отделение в деревне Васюки открыто с 08:00. Однако, поскольку почтовые сотрудники знают, что к ним, кроме Сигизмунда, никто не ходит, то они устроили себе особый гибкий график работы, поделив день на интервалы работы и интервалы отдыха, и никому о нём не рассказывают.

Сигизмунд не знает график работы почты, но ему известно, что всякий раз его посылку будут разыскивать ровно K минут. При этом если по графику сотруднику до конца текущего рабочего интервала осталось меньше K минут, то он даже не станет пытаться искать посылку для Сигизмунда.

Заметим, что сотрудники почты в деревне Васюки гораздо отзывчивее, чем могло бы показаться на первый взгляд  − они выстраивают свой график работы таким образом, чтобы у Сигизмунда была хотя бы одна возможность в течение дня получить посылку. То есть длительность как минимум одного из рабочих интервалов  составляет не менее K минут.

К вам в руки случайно попал график работы почты в деревне Васюки. Посчитайте, сколько времени в худшем случае может простоять Сигизмунд на почте при условии, что ему всё же удастся получить посылку в этот день. Заметим, что Сигизмунд приходит на почту не раньше 08:00.

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

В первой строке входных данных содержится число N (1 ≤ N ≤ 20) − число интервалов работы сотрудников.

В следующих N строках содержится время начала и конца каждого из интервалов в формате 'ЧЧ:ММ ЧЧ:ММ'. Гарантируется, что интервалы упорядочены по времени, не пересекаются между собой, не начинаются раньше 08:00, между соседними интервалами есть хотя бы минута паузы.

В последней входной строке содержится целое число K − время в минутах на поиск посылки.

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

Выведите описание наихудшего случая похода Сигизмунда на почту − время прихода на почту и через пробел время получения посылки. Оба времени выводятся в формате 'ЧЧ:ММ' (см. примеры).

Если имеется несколько вариантов наихудшего случая, то выведите тот, у которого время прихода на почту самое раннее.

 

Пример ввода 1 4 08:00 08:42 09:00 10:10 15:12 17:43 17:44 17:59 60 Пример вывода 1 09:11 16:12

Пример ввода 2 3 08:00 08:01 08:02 08:03 08:04 08:05 1 Пример вывода 2 08:01 08:03