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

«Вам дана таблица размера N × M. Ваша задача — определить, встречается ли заданное слово в таблице. Считается, что в таблице встречается слово, если мы можем найти последовательно все его буквы, начав с какой-то клетки таблицы, и переходя от одной клетки таблицы к соседней по вертикали или горизонтали, при этом нельзя посещать одну клетку несколько раз.»

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

Спустя 2 месяца после олимпиады друзья получили письмо от организаторов ВКОШП с предложением составить задачи на следующий год! С тех пор молодые шаманы регулярно обмениваются своими задачами.

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

Егор быстро решил эту задачу, а Вы справитесь?

Для праздничного чаепития необходимо купить \(n\) пирожных. В магазине продается всего два вида пирожных, причем пирожных одного вида осталось \(a\) штук, а пирожных другого вида осталось \(b\) штук. Пирожные одного вида считаются одинаковыми. Сколькими способами можно купить ровно \(n\) пирожных?

Имеется 10 колб с водой и известен объем воды в каждой из них. За одно “касание” можно взять одну колбу и часть воды (или всю воду) из этой колбы разлить по одной или нескольким другим колбам в любом количестве. За какое наименьшее количество “касаний” можно уравнять объемы воды во всех колбах? Каждая колба может вместить любой объем воды.

Дорожка замощена плитками в один ряд, плитки пронумерованы числами от 1 до 1000. На плитках с номерами \(A\), \(B\) и \(C\) (\(A \lt B \lt C\)) сидят три кузнечика, которые играют в чехарду по следующим правилам:

1. На одной плитке может находиться только один кузнечик.

2. За один ход один из двух крайних кузнечиков (то есть с плитки \(A\) или с плитки \(C\)) может перепрыгнуть через среднего кузнечика (плитка \(B\)) и встать на плитку, которая находится ровно посередине между двумя оставшимися кузнечиками (то есть между \(B\) и \(C\) или \(A\) и \(B\) соответственно). Если между двумя оставшимися кузнечиками находится чётное число плиток, то он может выбрать любую из двух центральных плиток.

Например, если кузнечики первоначально сидели на плитках номер 1, 5, 10, то первым ходом кузнечик с плитки номер 10 может перепрыгнуть на плитку номер 3 (она находится посередине между 1 и 5), или кузнечик с плитки номер 1 может перепрыгнуть на плитку номер 7 или 8 (эти две плитки находятся посередине между плитками 5 и 10).

Даны три числа: \(A\), \(B\), \(C\). Определите, какое наибольшее число ходов может продолжаться игра.