22179번 - Загранпаспорт 다국어

Многим знакома ситуация, когда для получения какого-либо документа, например, загранпаспорта, требуется в строго определенном порядке обойти несколько мест, в каждом из которых требуется совершить какое-либо действие: получить справку, написать заявление, заверить ксерокопию и т.д. Для удобства граждан такие места стали объединяться в единые центры, где каждое место превращается в отдельное окно. Но все равно есть проблема: каждое окно имеет свой режим работы.

Один человек планирует придти за своим загранпаспортом в hh часов mm минут. Он знает, что ему требуется обойти в определенном порядке ровно n окон, и знает их режим работы. В конце обслуживания в последнем из них он получит загранпаспорт. Человек хочет узнать, успеет ли он получить паспорт до конца дня, если кроме него в едином центре не будет других посетителей.

Про каждое окно известно его время открытия и время закрытия. Также известно, сколько минут занимает обслуживание одного посетителя в каждом окне.

Считается, что посетитель подходит к окну в начале некоторой минуты. Время открытия окна — это первая минута, во время которой оно уже работает, а время закрытия — первая минута, когда оно уже не работает. Например, если окно открывается в 12:00 и закрывается в 20:00, а обслуживание занимает 11 минут, то если человек подошел к окну между 12:00 и 19:49, включительно, то его обслужат сразу, если в 11:59 или раньше, то его начнут обслуживать в 12:00, а если в 19:50 или позже, то его уже не обслужат.

Человек перемещается между окнами мгновенно. Таким образом, например, если обслуживание в некотором окне занимает 10 минут, и человек подошел к нему в 12:45, то обслуживание в следующем окне для него может начаться в 12:55 или позже.

Все окна открываются не раньше, чем в 00:00, и закрываются не позже, чем в 23:00. В окне не обслуживают посетителя, если до конца рабочего времени окна осталось меньше времени, чем требуется на обслуживание.

Требуется выяснить, успеет ли человек получить загранпаспорт, и если да, то в какой самый ранний момент времени он сможет покинуть единый центр, получив загранпаспорт.

Первая строка содержит время, когда человек планирует придти в единый центр, в формате hh:mm. Вторая строка содержит одно целое число n — количество окон, которые требуется обойти (1 ≤ n ≤ 100).

Следующие n строк содержат описание работы всех окон в том порядке, в котором их нужно обходить. Строка, описывающая окно номер i, содержит время открытия этого окна в формате hh:mm, затем через пробел время закрытия в том же формате, и через пробел одно целое число t_i — количество минут, которые займет обслуживание посетителя в этом окне (1 ≤ t_i ≤ 1440). Время закрытия каждого окошка строго больше времени его открытия.

В случае, если человек успеет получить загранпаспорт, выведите в первой строке Yes, а во второй — время, когда он сможет покинуть единый центр в формате hh:mm. Иначе выведите в первой строке No.