Жюри N-ской олимпиады по информатике решило зашифровать свои материалы подстановочным шифром. Для шифрования таким шифром задаётся взаимно-однозначное соответствие между буквами алфавита в открытом (т.е. до шифрования) тексте и буквами алфавита в закрытом (т.е. после шифрования) тексте, это соответствие и является ключом шифра. В процессе шифрования каждая буква в открытом тексте заменяется на соответствующую ей букву в закрытом тексте, порядок букв в слове при этом не меняется.

Однако, память у членов жюри оказалась уже не та, что в молодые годы, поэтому часто они путали, какие буквы надо было заменять на какие. В результате теперь они не могут восстановить свои материалы, а олимпиада уже на носу!

Чтобы разрешить свои проблемы, они обратились к вам. Для облегчения вашей задачи они выписали на бумажку все возможные варианты зашифрования букв, которые они могли применять, в виде набора пар «открытая буква» — «зашифрованная буква». Также вам известны все пары букв N-ского алфавита, которые могут следовать одна за другой в открытом тексте. Ваша задача состоит в том, чтобы по заданному зашифрованному слову сказать, соответствует ли ему хоть одно расшифрованное слово, единственен ли вариант расшифровки, и привести пример вариантов расшифровки слова. Слово \(\mathcal{A}\) считается возможной расшифровкой слова \(\mathcal{B}\), если, во-первых, его можно «зашифровать» (заменяя каждую букву на одну из соответствующих ей «зашифрованных» букв), получив слово \(\mathcal{B}\), и, во-вторых, каждая пара букв слова \(\mathcal{A}\), стоящих рядом, является допустимой для N-ского языка.

Капитаны Флинт и Джек Воробей нашли клад и хотят поделить его. Клад находится в шкатулке и состоит из чётного числа драгоценных камней. Капитан Флинт оценил \(i\)-ый камень в \(a_i\) пиастров, а Джек Воробей — в \(b_i\) долларов. Теперь они действуют следующим образом. Джек Воробей достаёт из шкатулки два камня, после чего Флинт забирает себе один из них (естественно, тот, у которого больше \(a_i\)). Оставшийся камень достаётся Воробью. После этого Джек Воробей достаёт ещё пару камней, и так далее: каждым ходом Воробей достает из шкатулки два камня, Флинт забирает себе камень с большим \(a_i\), оставшийся камень достается Воробью.

Джек Воробей знает все \(a_i\), все \(b_i\), а также может, доставая очередные два камня, подглядеть в шкатулку и выбрать, какие именно камни надо доставать. Помогите ему действовать так, чтобы доля Воробья была максимально возможной (т.е. чтобы сумма \(b_i\) полученных Воробьём камней была как можно больше).

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

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

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

Система дорог в области устроена следующим простым образом. Есть \(N\) населённых пунктов, некоторые из которых соединены дорогами. Между каждой парой пунктов существует не более одной дороги, и более того, для каждой пары населённых пунктов есть ровно один способ добраться из одного в другой (возможно, через промежуточные посёлки).

В каждом населённом пункте можно разместить ремонтную подстанцию. В принципе, фирма может размещать как крупные подстанции, которые даже в одиночку смогут обслуживать всю область, но при этом будут требовать больших расходов на содержание, так и небольшие станции, которые будут обслуживать лишь прилегающие населённые пункты, но при этом будут обходиться намного дешевле. Фирма уже определила, что каждую подстанцию можно характеризовать параметром “мощность”, которая может принимать значения, являющиеся целыми положительными числами (равна нулю мощность быть не может). Подстанция с мощностью \(k\) будет обслуживать населённый пункт u, в котором она расположена, и все другие населённые пункты, до которых можно добраться из u, использовав не более k дорог (т.е. при \(k\)=1, например, подстанция обслуживает свой населённый пункт и все, которые напрямую соединены с ним дорогой). Стоимость содержания такой подстанции пропорциональна её мощности.

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

Как показывает статистика, автобусы намного реже ломаются на дорогах, чем внутри населённых пунктов, где они вынуждены часто изменять скорость, останавливаться, трогаться с места, заводить двигатель и т.д., поэтому не важно, все ли дороги обслуживаются — главное, чтобы обслуживались все населённые пункты.

Оценив последние успехи вашего друга в экономическом отделе компании, владеющей сетью маршрутных такси, директор повысил его до главного диспетчера. Теперь друг указывает, на какой маршрут должна выходить та или иная маршрутка.

В автопарке компании есть \(n\) маршруток, \(i\)-ая маршрутка номинально вмещает \(a_i\) пассажиров. По договору с департаментом транспорта города компания обязана обслуживать \(m\) маршрутов. Накопленная статистика говорит, что оптимальнее всего, если \(j\)-ый маршрут обслуживает такси номинальной вместимостью \(b_j\) пассажиров. Каждая маршрутка приписывается не более чем к одному маршруту, каждому маршруту приписывается не более одной маршрутки.

Разумеется, каждый уважающий себя диспетчер при назначении маршруток на маршруты старается минимизировать потери, которые бывают следующими:

• если \(i\)-ая маршрутка обслуживает \(j\)-ый маршрут, то компания теряет \(|a_i-b_j|\) у.е., так как чем меньше заполнено такси, тем больше не используются его возможности, а чем больше переполнено такси, тем чаще его приходится ремонтировать;
• от каждой простаивающей маршрутки, то есть такой, которой не назначен ни один маршрут, компания несет убыток \(p\) у.е.;
• компании приходится платить штраф \(q\) у.е. департаменту транспорта за каждый не обслуживаемый маршрут.

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

В игре «Руммикуб» используются фишки, которые бывают четырех различных цветов, и на каждой из которых написано одно натуральное число от 1 до 13. Для каждого числа и для каждого цвета в наборе фишек есть ровно две соответствующие фишки, т.е. всего в наборе \(8\cdot 13 = 104\) фишки.

Число, написанное на фишке, будем называть ее достоинством; цвета будем обозначать латинскими буквами A, B, C и D, и каждую фишку будем обозначать, записывая сначала ее цвет, а потом — ее достоинство. Например, C12 — это фишка цвета C и достоинством 12.

Комбинацией в игре называется набор из как минимум трех фишек, удовлетворяющий любому из следующих условий:

• Достоинства всех фишек одинаковы, а цвета — попарно различны; или
• Цвета всех фишек одинаковы, а достоинства являются последовательными натуральными числами.

Например, следующие наборы фишек являются комбинациями:

• C12, A12, B12;
• C12, A12, B12, D12;
• C5, C6, C7;
• A3, A4, A5, A6, A7.

При этом следующие наборы не являются комбинациями:

• A3, B3 (слишком мало фишек);
• A3, B3, C3, D3, B3 (цвета повторяются);
• A3, A4, A4, A5, A6 (достоинства повторяются);
• A3, A4, A6, A7, A8 (число 5 пропущено).

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