Недавно Аркадий перешел на работу диспетчером в крупный аэропорт. Он контролирует взлетно-посадочную полосу, которая обычно используется только для посадок. Поэтому у него есть расписание посадок на ближайшее время, каждая посадка продолжается $$$1$$$ минуту.
Аркадия попросили вставить в расписание один взлет. Взлет также занимает $$$1$$$ минуту, но по соображениям безопасности требуется, чтобы между взлетом и любой посадкой было хотя бы $$$s$$$ минут паузы с обеих сторон.
Найдите ближайшее время, в которое Аркадий может вставить взлет.
Первая строка содержит два целых числа $$$n$$$ и $$$s$$$ ($$$1 \le n \le 100$$$, $$$1 \le s \le 60$$$) — количество посадок в расписании и минимальный допустимый интервал между посадкой и взлетом.
Каждая из следующих $$$n$$$ строк содержит два целых числа $$$h$$$ и $$$m$$$ ($$$0 \le h \le 23$$$, $$$0 \le m \le 59$$$) — время, в часах и минутах от текущего времени, когда будет садиться очередной самолет (таким образом текущее время $$$0$$$ $$$0$$$). Все времена даны в порядке возрастания.
Выведите два целых числа $$$h$$$ и $$$m$$$ — час и минуту от текущего времени, когда Аркадий может вставить взлет.
6 60
0 0
1 20
3 21
5 0
19 30
23 40
6 1
16 50
0 30
1 20
3 0
4 30
6 10
7 50
9 30
11 10
12 50
14 30
16 10
17 50
19 30
21 10
22 50
23 59
24 50
3 17
0 30
1 0
12 0
0 0
В первом примере обратите внимание, что между временами 1:20 и 3:21 недостаточно времени, так как и взлет, и посадка занимают одну минуту.
Во втором примере в расписании нет свободных мест, поэтому Аркадий вынужден запланировать взлет после всех посадок. Обратите внимание, возможно, что ему придется запланировать взлет на более, чем $$$24$$$ часа от текущего времени.
В третьем примере Аркадий может вставить взлет даже до первой посадки.
Название |
---|