В новом учебном году на занятия в компьютерные классы Дворца Творчества Юных пришли учащиеся, которые были разбиты на N групп. В i-й группе оказалось X_i человек. Тут же перед директором встала серьезная проблема: как распределить группы по аудиториям. Во дворце имеется M ≥ N аудиторий, в j-й аудитории имеется Y_j компьютеров. Для занятий необходимо, чтобы у каждого учащегося был компьютер и еще один компьютер был у преподавателя. Переносить компьютеры из одной аудитории в другую запрещается. Помогите директору!

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

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

Возьми шахматную доску и поставь на нее коня. На ту клетку, на которую ты поставишь коня, я положу 2^K золотых монет. На те клетки, на которые ты сможешь дойти конем за 1 ход, я положу 2^K-1 золотых монет. И вообще, если с клетки, на которую ты поставишь коня, ты сможешь дойти до некоторой клетки самое меньшее за P ≤ K ходов, я положу на нее 2^K-P золотых монет. Но если ты проявишь чрезмерную жадность и не сможешь унести все монеты, которые я выложу на доску, то я прикажу отрубить тебе голову!

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

Примечание

Напоминаем, что шахматная доска имеет форму квадрата 8 на 8 клеток, столбцы называются латинскими буквами от a до h, а строки – цифрами от 1 до 8, клетка имеет название в виде пары буква-цифра, в зависимости от того, на пересечении какого столбца и какой строки она находится.

Конь ходит буквой "Г" – на 2 клетки в горизонтальном или вертикальном направлении и затем на одну клетку в перпендикулярном направлении. Разумеется, конь не может выходить за пределы доски.

Шахматная доска и возможные ходы коня в одной из позиций изображены на рисунке.

Правительство страны Ректилании решило построить новый город. По плану правительства, город должен быть построен на сетке M на N прямоугольных участков, размером 100 на 100 метров. Все улицы должны иметь ширину 100 метров и занимать соответственно одну горизонталь или вертикаль сетки. Вертикальные улицы должны пролегать по вертикалям с номерами X₁...X_V, горизонтальные – по горизонталям с номерами Y₁...Y_H. При этом улицы не соприкасаются, то есть не бывает X_i = X_i-1 + 1 и соответственно Y_j = Y_j-1 + 1 .

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

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

Клуб Юных Хакеров разработал новый язык для web-страниц. В этом языке у тегов нет атрибутов, и запрещается использовать пробелы в написании тега. А именно: назовем открывающим тегом языка HTHL (Hyper Text Hackers' Language) следующую последовательность:

"<", имя тега, ">"

а закрывающим  тегом последовательность

"</", имя тега, ">"

где имя тега – любая последовательность латинских букв и цифр, не длиннее 100 символов. Рассмотрим примеры тегов языка HTHL:

<b> <par> <hthl> <hacker2> <super>

</i> </hthl> </br> </hyper> </down>

При написании браузера для просмотра своих страниц, юные хакеры столкнулись с проблемой поиска слова на странице. Ведь некоторые теги (в примере - <b>, <i> и <u>) и соответствующие закрывающие теги (в примере - </b>, </i> и </u>) не разрывают слово. Например, при поиске слова hello комбинация h<b><i>el</i>l</b>o должна быть найдена. Ваша задача состоит в том, чтобы помочь юным хакерам в решении нелегкой проблемы поиска.