Между пунктами с номерами 1, 2, ... , N(N ≤ 1500) проложено несколько дорог. Длина каждой дороги известна. По этой системе дорог можно добраться из любого упомянутого пункта в любой другой. Автозаправки расположены только в пунктах. Требуется определить, какое максимальное расстояние без заправки должен быть в состоянии проезжать автомобиль, чтобы без проблем передвигаться между пунктами.

В телеигре "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, при котором игрок может воспользоваться заведомо выигрышной стратегией.

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

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

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

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

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

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