В компании MacroHard в последнее время резко участились опоздания сотрудников. Проанализировав ситуацию, руководство решило, что это вызвано большим разбросом в показаниях наручных часов сотрудников. После дополнительного совещания руководящего состава было постановлено, что все сотрудники должны перевести часы на одно и то же время (не важно какое).
Все сотрудники компании носят исключительно электронные часы одного образца. Время на них отображается в формате HH:MM:SS (где HH — часы, MM — минуты, SS — секунды, всегда отображаются в виде двух цифр, 00≤HH≤23, 00≤MM≤59, 00≤SS≤59). Перевод часов осуществляется с помощью двух кнопок. Первая кнопка меняет поле редактирования следующим образом: после первого нажатия часы переходят из режима отображения времени в режим редактирования поля HH, после второго — в режим редактирования поля MM, после третьего — в режим редактирования поля SS, а после четвертого возвращаются в режим отображения времени и т.д. по циклу. Каждое нажатие второй кнопки приводит к увеличению редактируемого поля на единицу (в режиме отображения времени ничего не происходит). При переполнении секунд поле SS обнуляется, а MM увеличивается на единицу, при переполнении минут поле MM обнуляется, а HH увеличивается на единицу, а при переполнении часов просто обнуляется поле HH.
И все бы хорошо, но, в силу своей природной лени, сотрудники хотят минимизировать суммарное число нажатий кнопок при переводе часов. При этом после перевода часов все часы должны оказаться в режиме отображения времени, в начале все часы также находятся в этом режиме.
Напишите программу, определяющую минимальное суммарное количество нажатий кнопок, достаточное для перевода часов всеми сотрудниками к одному времени.
Первая строка входных данных содержит натуральное число N (1≤N≤200) — количество сотрудников компании. Последующие N строк содержат показания часов каждого из сотрудников в формате "HH:MM:SS".
Выведите одно число — минимальное суммарное количество нажатий.
Система оценки 1 балл получат программы, правильно решающие задачу при ограничении 1≤N≤2.
2 08:01:01 07:59:00
7
В кассовом зале вокзала внедрили систему «электронная очередь». Теперь пассажир, который хочет купить билеты, при входе в зал получает талончик, после чего ожидает, когда подойдет очередь, и его пригласят к освободившейся кассе.
Система «электронная очередь» работает следующим образом. В зале имеются N касс, которые работают все время, за исключением времени перерывов (время перерывов в каждой кассе свое). Пассажиры приглашаются к кассам строго в порядке получения ими талончиков. Каждый пассажир проводит у кассы 5 минут (которые уходят на выбор поезда и оплату заказа), плюс оформление каждого билета дополнительно занимает еще одну минуту (таким образом, если пассажир, например, хочет оформить 3 билета, то он проведет у кассы 8 минут). Если пассажир был приглашен к кассе в момент времени A, а оформление его займет K минут, то и он, и эта касса освободятся к моменту времени A+K+1.
В освободившуюся кассу направляется очередной покупатель, если только в этой кассе не должно быть перерыва в ближайшие 5 минут. Но если касса начала оформление заказа какого-то пассажира, то она завершает оформление этого заказа, даже если в ней в процессе оформления должен начаться перерыв. При этом перерыв не сдвигается (то есть начинается на некоторое время позднее, но заканчивается ровно во столько, во сколько и должен). Считается, что если перерыв в кассе с момента A до момента B, то касса, освобождаясь в момент (A–5) начинает обслуживание очередного покупателя, а освобождаясь в моменты (A–4), (A–3), и так далее, — не начинает, а первого покупателя после перерыва касса начнет обслуживать в момент (B+1).
Если одновременно освобождается сразу несколько касс, то первый по очереди попадает в кассу с меньшим номером, второй — в следующую и т.д. Если в момент, когда касса освобождается, в очереди нет пассажиров, касса, естественно, никого не обслуживает. В этом случае, как только новый пассажир приходит и встает в очередь, он тут же попадает на обслуживание в свободную кассу с минимальным номером.
Напишите программу, которая по информации о времени прихода каждого пассажира и о количестве билетов, которые он собирается купить, выведет время, когда этот пассажир покинет кассовый зал.
Ни один пассажир не покупает больше 10 билетов, никакие два пассажира не приходят в кассовый зал в один и тот же момент времени, между концом одного перерыва и началом следующего перерыва у одной кассы проходит не менее 60 минут, длительность каждого перерыва не менее 15 минут.
Сначала вводятся количество касс \(N\) и и количество пассажиров \(M\) (1 ≤ \(N\) ≤ 30, 1 ≤ \(M\) ≤ 10000). Далее идет описание перерывов каждой кассы: оно начинается с числа \(C_k\) (1 ≤ \(k\) ≤ \(N\)) — количество перерывов у данной кассы (0 ≤ \(C_k\) ≤ 5), а далее идут \(C_k\) пар чисел, задающих время начала перерыва и его длительность. Перерывы каждой кассы перечислены в порядке наступления.
Далее заданы \(M\) пар чисел, задающих время прихода очередного пассажира и количество билетов, которые он собирается купить. Пассажиры перечислены в порядке их прихода.
Все времена и длительности — натуральные числа, не превышающие 100000.
Для каждого пассажира выведите два числа — номер кассы, которая будет его обслуживать, и время, в которое он покинет кассовый зал, купив нужные ему билеты.
Примеры
| Вход | Выход | Комментарий |
| 1 2 1 10 15 1 1 2 2 | 1 7 1 32
| Имеется единственная касса с перерывом с 10-ю по 24-ю минуты. Первый пассажир будет сразу обслужен, его оформление закончится в 7 минут. За это время придет второй пассажир, однако до перерыва единственной кассы останется 3 минуты, поэтому она не будет никого принимать до его окончания. Второй пассажир будет принят только на 25 минуте и освободится в 32. |
| 2 7 2 10 15 305 15 1 5 15 1 1 2 2 100 3 101 1 300 1 301 1 302 1 | 1 7 2 27 1 108 2 107 1 306 2 307 2 313 | Первый пассажир сразу пойдет в первую кассу, она оформит его к 7-й минуте и не будет никого принимать до 25-й минуты в связи с перерывом. По той же причине вторая касса не сможет никого принять до окончания ее перерыва. На 20-й минуте к ней поступит второй пассажир. К 100-й минуте обе кассы будут свободны, поэтому пришедших в 100-ю и 101-ю минуты сразу пригласят к кассам (третьего – к минимальной по номеру свободной). На 300-й минуте пятый пассажир начнет оформляться в первой кассе, после чего она сразу закроется на перерыв до 320-й минуты. Шестому и седьмому пассажиру не остается ничего, кроме как обращаться во вторую кассу. |