Завтра Петя уезжает в кругосветное путешествие, в процессе которого собирается посетить N разных городов. Вспомнив о старинной традиции бросать монетки в фонтаны для того, чтобы когда-нибудь вернуться в это место, он решил запастись монетами заранее. Поскольку это всего лишь традиция, подумал Петя, то с него хватит оставить в каждом городе по одной копеечной монете – зачем тратиться зря?

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

С этими мыслями Петя решил прогуляться до продуктового магазина – купить в дорогу немного еды. Из всего ассортимента ему подходило M видов товара (количество товаров каждого вида неограниченно), стоимость i-го равна a_i рублей b_i копеек. И тут его осенило. Если покупать товары в правильной последовательности, то он довольно быстро сможет скопить так нужные ему N копеечных монет!

Процесс покупки в магазине устроен следующим образом. Петя может заказать любой набор из подходящих ему товаров (каждого товара Петя может взять сколько угодно единиц). После чего он платит за них и получает сдачу минимальным числом купюр и монет (любых монет и купюр в кассе также с избытком). Это означает, например, что если ему должны сдать 11 рублей и 98 копеек сдачи, то он получит купюру в 10 рублей, монеты в 1 рубль, 50 копеек, 4 монеты в 10 копеек, одну монету в 5 копеек и три копеечных монеты. При этом он волен вносить любую сумму (лишь бы она была не меньше требуемой для оплаты) и платить любым набором купюр и монет, имеющихся у него в распоряжении.

После этого Петя может ещё раз подойти к кассе, сделать заказ, расплатиться имеющимися наличными (можно использовать и полученные до этого со сдачей) и так далее сколько угодно раз.

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

Комментарий для нероссийских участников олимпиады.

В России используются монеты и купюры достоинством 1, 5, 10, 50 копеек и 1, 2, 5, 10, 50, 100, 500, 1000 и 5000 рублей. 1 рубль равен 100 копейкам.

В начале XIX века еще не было самолетов, поездов и автомобилей, поэтому все междугородние зимние поездки совершались на санях. Как известно, с дорогами в России тогда было даже больше проблем, чем сейчас, а именно на N существовавших тогда городов имелась ровно N-1 дорога, каждая из которых соединяла ровно два города. К счастью, из каждого города можно было добраться в любой другой (возможно, через некоторые промежуточные города). В каждом городе имелась почтовая станция (или, как ее называют, «ям»), на которой можно было пересесть в другие сани. При этом ямщики могли долго запрягать (для каждого из городов известно время, которое ямщики в этом городе тратят на подготовку саней к поездке) и быстро ехать (также для каждого города известна скорость, с которой ездят ямщики из него). Можно считать, что количество ямщиков в каждом городе не ограничено.

Если бы олимпиада проводилась 200 лет назад, то путь участников занимал бы гораздо большее время, чем сейчас. Допустим, из каждого города в Москву выезжает участник олимпиады и хочет добраться до Москвы за наименьшее время (не обязательно по кратчайшему пути: он может заезжать в любые города,  через один и тот же город можно проезжать несколько раз). Сначала он едет на ямщике своего города. Приехав в любой город, он может либо сразу ехать дальше, либо пересесть. В первом случае он едет с той же скоростью, с какой ехал раньше. Решив сменить ямщика, он сначала ждет, пока ямщик подготовит сани, и только потом едет с ним (естественно, с той скоростью, с которой ездит этот ямщик). В пути можно делать сколько угодно пересадок.

Жюри стало интересно, какое время необходимо, чтобы все участники олимпиады доехали из своего города в Москву 200 лет назад. Все участники выезжают из своих городов одновременно.

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

Майор понимал, что у него совсем немного времени до того, как придут и за ним. Поэтому он выбрал некоторый кусок документа и переслал Вам, своему ближайшему соратнику по борьбе со злом (майор боялся, что не хватит времени отправить документ целиком). Сразу после этого к нему ворвались злоумышленники и схватили Пронина. Чтобы не вызывать никаких подозрений, преступники решили не удалять документ, а просто закодировать его некоторым образом. Известно лишь, что каждый символ был заменён ровно на один символ, при этом разные символы перешли в разные, одинаковые – в одинаковые. Известно, что и до, и после перекодировки документ состоял только из символов с ASCII-кодами от 32 до 255 включительно.

Получив часть документа S, Вы немедленно отправились выручать Пронина из беды, но его дом оказался пуст. На его компьютере остался закодированный документ. Ни майор, ни его коллега на связь не выходят. Вы поняли, что единственный способ отыскать их – проникнуть на главную фабрику организации. Для этого необходимо раскодировать весь документ. Прежде чем передать его лингвистам, нужно произвести техническую обработку.

Возможно, что в тексте есть несколько фрагментов, которые могут являться кодом имеющегося у вас фрагмента S. Вы наудачу предположили, что имеющийся у вас фрагмент S в закодированном тексте является самым первым из фрагментов, в которые он мог быть закодирован.

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