В телеигре "The Price is Right" игроки (обычно четверо) соревнуются в угадывании стоимости того или иного предмета. Побеждает тот, кто назвал наиболее близкое число, не превосходящее ответа. Ввиду популярности телеигры "Кто Хочет Стать Миллионером", в которой участвует один игрок, American Contest Management (ACM) решило выпустить свою версию игры «The Price is Right» для одного игрока. В этой версии каждому участнику даётся G (1 ≤ G ≤ 30) попыток и L (0 ≤ L ≤ 30) жизней. Игроку требуется точно угадать стоимость предмета. Если очередная попытка верна, то игрок выигрывает. В противном случае он теряет попытку. Помимо того, если он называет число, большее ответа, то также теряет одну жизнь. Игрок проигрывает, если у него не остаётся попыток или он называет большую стоимость, не имея ни одной жизни. Все цены положительные целые числа. Оказывается, что для некоторых значений G и L при условии, что искомая стоимость лежит в интервале от 1 до N включительно, можно избрать заведомо выигрышную стратегию. ACM не хочет, чтобы выигрывал каждый участник, поэтому организаторы хотят быть уверены, что настоящая стоимость превосходит N. Но в то же время нельзя делать игру слишком сложной, поскольку в противном случае победителей будет слишком мало, и игра быстро потеряет популярность. Поэтому организаторы хотят подобрать значения G и L в зависимости от искомой стоимости. В связи с этим ACM попросило вас решить следующую задачу: по заданным значениям G и L найти максимальное значение N, при котором игрок может воспользоваться заведомо выигрышной стратегией.

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

Напишите программу, которая найдет минимальную стоимость такой сортировки заданной последовательности.

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

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

Будем называть пару строк (α, β) подпарой строки γ если γ = γ₁α γ₂β γ₃ для некоторых (возможно пустых) строк γ₁, γ₂, γ₃. Длиной пары строк будем называть сумму длин составляющих ее строк: |(α, β)| = |α| + |β|.

По заданным двум строкам ξ и η найдите их длиннейшую общую подпару, то есть такую пару строк (α, β), что она является подпарой как ξ, так и η, и ее длина максимальна.

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

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

Рассмотрим строку α. Будем говорить, что α мутирует в β, если α = xyz для некоторых (возможно пустых) x, y и z, а β = xy^Rz, где y^R означает строку y, записанную задом наперед (например, "abc"^R = "cba"). Будем говорить, что строки α и β похожи, если α может быть превращена в β не более чем за 4 мутации.

По двум данным фрагментам ДНК определите, похожи ли они.