Задача Электронная очередь

Описание

В кассовом зале вокзала внедрили систему «электронная очередь». Теперь пассажир, который хочет купить билеты, при входе в зал получает талончик, после чего ожидает, когда подойдет очередь, и его пригласят к освободившейся кассе.

Система «электронная очередь» работает следующим образом. В зале имеются 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). Далее идет описание перерывов каждой кассы: оно начинается с числа Ck (1 ≤ k ≤ N) — количество перерывов у данной кассы (0 ≤ Ck ≤ 5), а далее идут Ck пар чисел, задающих время начала перерыва и его длительность. Перерывы каждой кассы перечислены в порядке наступления.

Далее заданы M пар чисел, задающих время прихода очередного пассажира и количество билетов, которые он собирается купить. Пассажиры перечислены в порядке их прихода.

Все времена и длительности — натуральные числа, не превышающие 100000.

Формат выходных данных

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