Трамвайная линия имеет вид прямой. Петя живет в N трамвайных остановках от метро. Метро находится у нулевой остановки, в точке с координатой 0.

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

Компания MacroHard разработала новый язык программирования PASCAL++. В этом языке имеется оператор вывода PrintLn, с помощью которого можно выводить строки любой длины. По стандарту языка, разработанному специалистами компании, некоторые комбинации символов в строке должны при выводе играть особую роль:

Например, строка "New line\ntab\tslash\\\nA char \41, rus Б \81" должна была быть напечатана в следующем виде :

Напечатано	Здесь пробелы для наглядности обозначены символами 
New line tab slash\ A char A, rus Б Б	Newline tabslash\ AcharA,rusББ

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

В новом учебном году на занятия в компьютерные классы Дворца Творчества Юных пришли учащиеся, которые были разбиты на 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 клетки в горизонтальном или вертикальном направлении и затем на одну клетку в перпендикулярном направлении. Разумеется, конь не может выходить за пределы доски.

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