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

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

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

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

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

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

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

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

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

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

После того, как Принц поменяет лампы во всех комнатах, он перестанет их приобретать: лампы очень качественные и имеют большой срок службы.

Ваша задача — по заданному номеру месяца (от начала замен) и описанию комнат определить, в скольких комнатах уже произведена замена ламп и сколько ламп пока не нашло своего применения на конец этого месяца.

Дракон налил Принцессе ещё чашечку чая. Принцесса чуть заметно вздохнула и спросила:

— А принцессы и принцы в соседних замках — у них тоже договор аренды помещения?

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

Как рассказал Дракон, обитатели замков достаточно часто летают на драконах по разным делам. При этом они крайне не любят «пересекаться» друг с другом и требуют, чтобы по дороге их не видел никто из соседей. Так что диспетчеру, составляющему расписание полётов, приходится непросто.

Мы опишем упрощённую модель происходящего. Будем считать, что воздушное пространство поделено на n «воздушных коридоров». Эти коридоры занумерованы, и каждый из них располагается на определённой высоте: чем меньше номер коридора, тем он выше.

Дракон может начать полёт, заняв любой свободный коридор. Однако в ходе полёта дракон может только снижаться, притом только постепенно. Диспетчер требует, чтобы драконы осуществляли снижение только в целые моменты времени и только на один коридор вниз. Так, если дракон летит по воздушному коридору #j, он может переместиться в воздушный коридор #(j + 1) (если таковой существует). Если дракон занимает какой-либо воздушный коридор, он должен лететь в нём в течение хотя бы одной единицы времени.

В течение всего полёта дракон перемещается с постоянной горизонтальной скоростью, равной единице. Время перемещения между воздушными коридорами пренебрежимо мало и может быть положено равным нулю. Останавливаться в полёте дракон не может. У диспетчера имеется расписание, в котором для каждого воздушного коридора указано время, в течение которого этот коридор занят. Это время представлено множеством интервалов вида (s, f) (s < f); при этом считается, что в моменты времени s и f дракону будет разрешено занимать воздушный коридор, но ни в какие другие моменты времени между s и f он не может этого делать.

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

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

— А как же рыцари, которые спасают принцесс? Они тоже понарошку? — Принцесса выглядела грустной.

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

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

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

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

Поясним это более формально. Рассмотрим две пары (m₁, f₁) и (m₂, f₂). Предположим, что m₂ желал бы видеть своей парой f₁ более, чем f₂ (т.е. в списке m₂ номер f₁ меньше, чем f₂). Однако f₁ полагает, что m₁ лучший выбор, нежели m₂ (т.е. в списке f₁ номер m₁ меньше, чем m₂).

Если бы это было не так, то расклад устойчивым считать было бы уже нельзя: ведь m₂ и f₁ могли бы стремиться друг к другу.

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

Конечно, Дракон уже думал об этом раньше и пришёл к выводу, что для каждого возможного расклада можно ввести характеристику «недовольство». Мерой «недовольства» конкретного человека он считает номер его партнёра в паре в его списке. А мерой «недовольства» расклада — максимальный среди всех таких номеров.

Ваша задача — по заданным спискам предпочтений найти (устойчивый) расклад с минимально возможным «недовольством».

— А сами драконы именно так поступают, когда хотят найти себе пару? — спросила Принцесса.

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

Дракон рассказал Принцессе, что когда кто-то придумывает нового дракона, то в Долине Замков появляется новый замок, в котором и проживает вновь придуманный дракон. А когда дракона долго никто не тревожит, он впадает в спячку.

Иногда в Долине Замков идёт необычный дождь: на небе ни облачка, ярко светит солнце, и только крупные частые капли стучат по крыше замка, в котором уснул дракон. А когда дождь заканчивается, на месте этого замка окажется лужайка с полевыми цветами. Более того, ручейки дождевой воды бегут по дорожкам, что ведут от этого замка. Если дорожка приводит к замку с бодрствующим драконом, то ручеёк останавливается. Если же на пути ручейка встречается замок с уснувшим драконом, замок тоже превратится в лужайку, а ручеёк побежит дальше.

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

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

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

— Не совсем так, — уточнил Дракон. — Никто не хочет незапланированных встреч. А вот, скажем, на какое-нибудь интеллектуальное состязание все охотно собираются. Есть игры, где команда состоит из двух человек...

Дракон рассказал Принцессе, что скоро в Долине Замков начнутся квалификационные соревнования по Игре в Слова. Команды, набравшие наибольшее количество очков, будут участвовать в следующем круге соревнований. При равном количестве очков более высокое место занимает команда, которая потратила меньше времени.

Опишем, как проходит квалификационная игра для одной команды.

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

Сначала ведущий выдаёт одну карточку Первому Игроку. Первый Игрок пробует объяснить слово, записанное на карточке, Второму Игроку, не называя это слово. Когда объяснение закончено, Второй Игрок сообщает свой ответ. Если ответ Второго Игрока совпадает со словом на карточке, команде засчитывается очко. Далее ведущий выдаёт одну карточку Второму Игроку, и уже тот объясняет записанное на карточке слово Первому Игроку. Потом карточку вновь получает Первый Игрок... Игра продолжается, пока не закончатся карточки.

В этом сезоне в квалификационных играх есть важное дополнение к описанным выше правилам. При объяснении очередного слова игрок может использовать терминологию только одной предметной области. Более того, использовать терминологию некоторой предметной области в квалификационной игре можно только один раз. В правилах выделено n (n ≥ m) предметных областей.

Пара игроков X и Y, собирающаяся участвовать в квалификационной игре, очень много готовилась. Они полагают, что любой игрок пары угадает любое слово, объясняемое терминами любой предметной области. Вопрос только во времени, которое на это понадобится.

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

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

— Хорошая игра, — Принцесса произнесла это немного отстранённо; было понятно, что она думает о чём-то другом.

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

Принцесса А. предложила Рыцарю сыграть с ней в игру с числами. Она записала на листе бумаги число 0. Назовём это число текущим результатом.

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

Принцесса А. выполняет действие, предложенное Рыцарем, и вычисляет полученное значение. Это значение и становится новым текущим результатом.

Принцесса А. желает, чтобы текущий результат всегда был не меньше нуля и не больше k. Игра заканчивается, когда Рыцарь не может сделать очередной ход (т.е. любое действие приводит к выходу за границы указанного диапазона) или же когда принцесса А. исчерпает задуманную ей последовательность из n чисел.

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

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

— А Принц — в какие игры он играет? — Принцесса внимательно смотрела на Дракона.

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

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

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

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

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

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

Принц решил, что ему недостаёт некоторых знаний и навыков. Он определил, что в первую очередь хочет приобрести знания и навыки в n сферах деятельности. Затем он выяснил, что существует m₁, m₂, ..., m_n курсов и тренингов по каждой из интересующих его сфер деятельности. Принц внимательно изучил описания курсов и тренингов и составил таблицу, в которой элемент s_ij обозначает, на какую величину он может улучшить свои знания и навыки в сфере деятельности #i, если запишется на курс #j (j = 1, 2, ..., m_i).

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

Ваша задача — определить, на какие курсы следует записаться Принцу.

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

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

Однажды он наблюдал за одним рыцарем, любителем играть. Он даже организовал целый клуб любителей игры. Сначала в этом клубе было n участников.

Когда этот рыцарь собирался играть, то он выбирал тип партии и отправлял сообщения своим знакомым из клуба с приглашением поиграть. Эти знакомые пересылали сообщения своим знакомым, и информация о предстоящей игре распространялась среди членов клуба.

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

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

— Дело не в играх, — Дракон всё же решил, что не стоит говорить про тренинги. — Нужно, чтобы он захотел насовсем уйти из Долины Замков.

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

— Лучше говорить, что ничего для него не изменится, если он уйдёт из Долины, — прервал размышления Принцессы Дракон.

Принцесса уже давно решила, что она скажет Принцу. Но Дракон, выслушав Принцессу, понял, что в таком виде рассказ вряд ли убедит Принца покинуть Долину. Он уже хорошо изучил Принца и понимал, что не все аргументы Принцессы покажутся Принцу аргументами «за».

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

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

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

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

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

— Кажется, мы с ним немного знакомы, — улыбнулась Принцесса, — А встретиться случается редко: разные люди, разные интересы...

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

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

Ваша задача — определить, в скольких вопросах Принцесса скорее согласится с Принцем, а в скольких — с Рыцарем.

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

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

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

В рецепте указано, сколько единиц того или иного ингредиента требуется для изготовления одного печенья. Конечно, Дракон хочет изготовить целое количество печений.

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

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