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

И самое обидное — узнал-то Пантелеймон об этом по чистой случайности. Из-за прорыва на теплотрассе министр безопасности принял решение, что прогулка царя будет проходить по запасному маршруту. А этот запасной маршрут проходит мимо пункта обмена валюты. В прошлый раз Дормидонту удалось убедить Пантелеймона, что на табло отображается температура воздуха, но то было летом, да и числа были в два раза меньше.

Размышления привели Дормидонта к выводу, что для начала надо бы перенести праздник ватрушкопечения. Этой идеей он поделился с министром времяисчисления Харитоном, и теперь они обдумывают, как это сделать.

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

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

• во-первых, все запланированные в году праздники должны состояться;
• во-вторых, никакие два праздника не должны состояться в один день;
• в-третьих, все назначаемые праздники должны состояться после тех праздников, которые указаны как их предшественники.

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

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

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

Пантелеймон рассказом проникся, даже велел указ заготовить — о расширении производства сметаны. Нельзя же такую выгоду упускать.

Пантелеймон полагает, что для начала надо увеличить производство сметаны на то количество s, которое Берендеев заводик производит. А чтобы по справедливости всё было, существующим предприятиям квоты раздать — разрешить увеличить производство на одинаковое для всех количество процентов. Вот только одна незадача: в настоящее время для закупок доступен только один тип линий по производству сметаны, рассчитанный на количество q, и изменить это количество никак не получится — технология...

Пантелеймон хочет определить увеличение производства на p процентов таким образом, чтобы в результате производство сметаны возросло на величину, максимально близкую к s по абсолютному значению. При этом предприятие не разрешается увеличивать производство более, чем на p процентов от текущего объема. Ваша задача — определить наиболее подходящее значение p.

И всё было бы хорошо, так нет же — министр промышленности Силантий возьми да и скажи, что отчего бы сметане подешеветь, ежели закваску у Берендея и покупаем. И пастеризаторы. И запчасти к ним. А упаковку у короля Сигизмунда. И хорошо, что министр экономики Калистрат начал про перспективы производства упаковки в царстве рассказывать, а то Силантий бы еще много чего перечислил.

Царь Пантелеймон заинтересовался, почему производство упаковки решили организовывать, а не, к примеру, пастеризаторов. Калистрат пояснил, что упаковка не только для сметаны годится. Так что начать решили с производства того продукта, который наибольшее влияние на другие оказывает. А пастеризаторы чуть позже производиться начнут — вот только упаковочный завод построим, так за другие возьмёмся.

Ведомство Калистрата определяет влияние следующим образом. Пусть для каждого продукта известно, какие продукты непосредственно требуются для его производства. Для каких-то из этих продуктов, в свою очередь, также известны те, что требуются для их производства (и т.д.) Также для каждого из продуктов известно, какая сумма потребуется на организацию его производства.

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

Ваша задача — определить этот продукт.

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

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

Ваша задача — определить, в каком городе следует построить завод.

Пока завод по производству упаковки ещё только в планах, а уж производство пастеризаторов даже и не запланировано, царь Пантелеймон озаботился: ежели конъюнктура хорошая, может, всё-таки надо прямо сейчас и увеличить производство сметаны да Берендеев заводик победить?

Так опять Силантий влез — для новых линий по производству новые помещения строить надобно. И коров новых заводить. И для новых коров тоже новые помещения строить...

Калистрат, конечно, вмешался: малый бизнес развивать надо. Вот завёл бы каждый житель по корове — и каково хорошо было бы. Участки с травой хоть завтра выделить всем можно — неудобий в царстве полно. И жители молоком бы себя обеспечили, и творогом, и сметаной. И мясом. Главный казначей Ферапонт заметил, что если мясом обеспечат, то молоком может и не получиться, но Калистрат и ухом не повёл, продолжил про индивидуальные хозяйства рассказывать...

Министр экономики предлагает выделить жителям участки площадью x и потребовать полностью их засеять кормовой травой. Будем полагать, что на единице площади всегда растёт ровно одна травинка. На прокорм одной коровы в сутки требуется m единиц длины травы.

В царстве произрастает n видов кормовых трав, и у каждой — своя скорость роста: k₁, k₂, ..., k_n единиц длины в сутки. Стоимость одного семечка (из которого вырастает ровно одна травинка) составляет g₁, g₂, ..., g_n соответственно. Также можно приобрести удобрения (для каждого вида травы — свой вид удобрений), которые могут увеличивать скорость роста травы. Стоимость единицы удобрения, которое нужно внести на единицу площади, чтобы увеличить скорость роста травы на единицу длины, определяется числами u₁, u₂, ..., u_n. Наконец, для каждого удобрения известно максимально возможное количество, которое можно внести на единицу площади: v₁, v₂, ..., v_n.

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

Царь Пантелеймон слушал Калистрата да поддакивал: раньше-то деды сметану делали без всяких новомодных пастеризаторов, и хорошая сметана была! И Дормидонт, министр финансов, идею одобрил: жители и молоком со сметаной себя обеспечат, да ещё налог на землю заплатят. А сметану, что заводы производят, всю на экспорт отправить можно будет.

Один Силантий только усомнился, что жители коров заведут, да сами сметану делать будут. Но у Калистрата ответ наготове: обяжем каждое домохозяйство сдавать сметану в стратегический фонд. Что тогда?

И Силантий не лыком шит: купят жители сухое молоко, что у короля Ганса хорошо делают, да закваску, что в царстве Берендея производится, вот и будет сметана, раз такой оброк на жителей наложен.

Выслушал это Пантелеймон и сказал, что решение простое. Запретить надо чужестранные продукты в царстве, наверняка в них вещества вредные содержатся и гены неправильные. Да и как иначе может быть, если в чужестранных яблоках червяки не водятся? А на возражения Силантия, что в царстве многие продукты не производятся, ответил, что замену найти им проще простого. Надо ли простому народу то же авокадо? — есть же огурцы, тоже зеленые, пупырчатые. А что внутри мякоть белая — так чисто картофель. Семечко внутри — в лесном орехе тоже внутри ядро, поменьше, конечно, но похоже!

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

Ваша задача — по описанию продукта получить разбиение, которое устроит Пантелеймона.

Пока Силантий с Калистратом поспорить пытался, главный казначей Ферапонт вычислял что-то. И вычислил: один Береднеев заводик сметаны-то больше производит, чем все местные заводы, вместе взятые.

Разгневался царь Пантелеймон не на шутку: как же так, заводик-то махонький с виду! Пусть министр науки и технологий объяснит! Министр Фалалей тут же успокоил: технологическое отставание сугубо временное, уже запланировано n грантов, в результате которых будут совершены открытия, это отставание ликвидирующие. А по некоторым позициям царство и вовсе окажется на переднем крае науки.

Существует k технологических направлений, которые планируется развивать. Изначально уровень развития каждого из этих k направлений (a₁, a₂, ..., a_k) будем считать равным нулю.

Выделение гранта может повысить уровень развития какого-либо направления на единицу при условии, что текущий уровень развития направления не превосходит уровень гранта (т.е. грант #j может повысить уровень развития направления #i в том случае, если текущее значение a_i ≤ g_j).

Министерство определило порядок выделения грантов. Очередной грант может быть выделен только тогда, когда завершён предыдущий. По заверениям Фалалея, после выполнения работ по всем грантам технологические направления будут иметь уровни развития не менее b₁, b₂, ..., b_k соответственно.

Ваша задача — сформировать план выделения грантов.

Главный казначей Ферапонт не преминул тут же у министра науки поинтересоваться: неужели открытия по плану-графику совершать можно? Министр науки Фалалей вопросу порадовался: начал хвалиться, какой в его министерстве документ разработали. Чтобы грант получить, надо каждый день работы подробнейше описать, множество показателей рассчитать: и какова площадь, приходящаяся на одного сотрудника, и используются ли энергосберегающие лампы, икакая поддерживается температура в помещении... И про сотрудников тоже многое сообщить нужно: и рост, и вес, и каковы спортивные достижения... А чтобы никаких сомнений в достоверности не было, каждый показатель записывается в бланк непременно от руки и подписью заверяется.

Министерство заранее не объявляет, какие значения показателей нужны для допуска к конкурсу грантов, поэтому научные группы сначала записывают реальные показатели. Когда выясняется, что требуется показатель, больший заявленного, то реальные показатели исправляют: говорят, что при переписывании с черновиков ошиблись. Конечно, не всякую цифру всякой заменить несложно. Ниже для каждой цифры приведён список тех, на которые её можно заменить. Более одного исправления не допускается. Например, нельзя исправить 6 на 9, сначала исправив 6 на 0.

• 0 — 6, 9
• 1 — 4, 7
• 2 — нет возможных исправлений
• 3 — 8
• 4 — 9
• 5 — 6, 8, 9
• 6 — 0
• 7 — 1, 4
• 8 — 2, 3, 5
• 9 — 0

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

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

Главный казначей Ферапонт чрезвычайно заинтересовался, каким образом, к примеру, спортивные достижения работника могут повлиять на его научные успехи. Министр промышленности Силантий заметил, что никак эти достижения не влияют, впрочем, как и большинство других показателей, что министерство науки видеть желает. И тому есть подтверждения.

Министр науки Фалалей сразу же возразил Силантию, что несколько специальных институтов организовано было, денно и нощно они трудились, чтобы показатели разработать, и продолжают трудиться — совершенствуют стандарты предоставляемой отчётности. Какие еще подтверждения?

На что Силантий ответил, что есть независимые источники, что исследования проводились, и что получились совсем другие результаты. Спором царь Пантелеймон заинтересовался, захотел про независимые источники узнать.

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

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

Более формально, если Силантий утверждает, что по данному показателю имеется исследование, то ему может быть начислено очко в двух случаях: когда он может привести ссылку (безотносительно запроса Фалалея) и когда он не может привести ссылку, но Фалалей не попросил её привести. В противном случае очко начисляется Фалалею. Считается, что Силантий переспорил Фалалея, если после обсуждения m показателей он набрал очков больше, чем его оппонент.

Конечно, Силантий не знает, будет ли просить привести ссылки царь. Но он готов рискнуть, чтобы переспорить Фалалея, и говорить, что некоторый показатель не влияет на научную деятельность в том случае, когда Фалалей не попросит приводить ссылку.

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

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

Фалалей рад был тему разговора сменить. Начал рассказывать, что серьёзные разработки по теории игр имеются. В частности, по антагонистическим играм. Да про такие вещи, конечно, на примере лучше рассказать.

Есть клеточное поле, некоторые его клетки считаются запрещёнными. Есть два игрока — для простоты и определённости назовем их Заяц и Волк. Изначально они находятся в разных (не запрещённых) клетках. Игроки ходят по очереди. Игрок может перемещаться из текущей клетки только в клетку, граничащую с текущей по стороне и не являющуюся запрещённой.

Первым ходит Заяц. Заяц может сделать ход в любом направлении или же остаться на месте.

Волк всегда делает ход по кратчайшему пути к текущему положению Зайца. При прочих равных направление движения Волк выбирает в следующем порядке: «влево», «вверх», «вправо», «вниз». Если путь от Волка до Зайца не существует, Волк остаётся на месте.

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

Ваша задача — сделать как можно больше ходов за Зайца.

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

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

Царь Пантелеймон немедленно воодушевился и предложил построить гостиницу как можно ближе к геотермальному источнику. Ну или во всяком случае на этой улице.

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

Калистрат и Фалалей в два голоса рассказывали, что с геотермальным источником надобно по науке поступить. Провести анализ воды — наверняка же минеральная. Грязь изучить — вдруг лечебная. Почвы рядом — быть может, лучше чуть в сторону сместить фонтан. Да и в других местах исследования провести — нельзя же исключить, что где-то поблизости дремлют и другие геотермальные источники. Конечно, надо институт почвоведения и грязелечения основать. Со всех царств и королевств соседних будут на курорт приезжать.

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

Министры выдвинули три предложения: отремонтировать теплотрассу, построить гостиницу и основать институт почвоведения и грязелечения. Обозначим эти предложения числами 1, 2 и 3 соответственно.

Каждый из n министров записал эти числа в порядке важности (по его мнению) выделения финансирования. Теперь главный казначей Ферапонт подсчитывает поданные голоса следующим образом: за первую позицию два очка, за вторую позицию одно очко и за третью позицию ноль очков.

Ваша задача — определить, сколько очков набирает каждое предложение.