чемпионаты Спб: Чемпионат СПб 2000

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

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

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

Примечание

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

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

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