Рассмотрим произвольную последовательность целых чисел. Между числами можно расставить знаки арифметических операций + или – , и таким образом получать некоторые выражения, которые принимают различные значения. Например, если взять последовательность: 17, 5,  - 21, 15, то можно получить восемь различных выражений:

Назовем последовательность делящейся на натуральное K, если + и – могут быть расставлены так, что итоговое значение выражения будет делиться на K. В приведенном примере последовательность делится на 7  (17 + 5 +  - 21 - 15 =  - 14), но не делится на 5.

Ваша задача — написать программу, определяющую делимость последовательности на целое число.

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

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

Цель игры — убрать карты в таком порядке, чтобы минимизировать общее количество набранных очков.

Например, если карты содержат числа 10, 1, 50, 20 и 5, игрок может взять карту с числом 1, затем 20 и 50, получая очки 10·1·50 + 50·20·5 + 10·50·5 = 500 + 5000 + 2500 = 8000. Если бы он взял карты в обратном порядке, то есть 50, затем 20, затем 1, количество очков было бы таким: 1·50·20 + 1·20·5 + 10·1·5 = 1000 + 100 + 50 = 1150.

(Задача отличается от предыдущых исключительно ограничениями.)

Есть сообщение, записанное в алфавите из N символов. Известно, что 1-й, 2-й, ..., N -й символы алфавита использованы в сообщении f ₁ , f ₂ , ..., f _N раз. Его необходимо набрать на M -клавишной клавиатуре, используя способ набора, аналогичный используемому в мобильных телефонах.

На телефоне, клавише 2 сопоставлены буквы abc, клавише 3 — def, и т.д. Для набора текста телефон переводится в специальный режим, в котором одно нажатие на клавишу 2 порождает символ a, 2 подряд нажатия на 2 символ b, 3 подряд символ c; аналогично, одно нажатие 3 порождает d, 2 подряд e и т. д. Если же необходимо набрать 2 подряд буквы a, то нажимают клавишу 2, немного ждут и снова нажимают клавишу 2.

В нашем случае, символы с 1-ого по некоторый K ₁ -ый должны соответствовать 1-ой клавише, с ( K ₁ + 1) -ого по некоторый K ₂ -ой — 2-ой клавише и т. д., до K _M = N . Конкретные значения K ₁ , K ₂ , ..., K _{M - 1} не задаются — их, наоборот, нужно подобрать.

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

(Задача отличается от предыдущых исключительно ограничениями.)

Есть сообщение, записанное в алфавите из N символов. Известно, что 1-й, 2-й, ..., N -й символы алфавита использованы в сообщении f ₁ , f ₂ , ..., f _N раз. Его необходимо набрать на M -клавишной клавиатуре, используя способ набора, аналогичный используемому в мобильных телефонах.

На телефоне, клавише 2 сопоставлены буквы abc, клавише 3 — def, и т.д. Для набора текста телефон переводится в специальный режим, в котором одно нажатие на клавишу 2 порождает символ a, 2 подряд нажатия на 2 символ b, 3 подряд символ c; аналогично, одно нажатие 3 порождает d, 2 подряд e и т. д. Если же необходимо набрать 2 подряд буквы a, то нажимают клавишу 2, немного ждут и снова нажимают клавишу 2.

В нашем случае, символы с 1-ого по некоторый K ₁ -ый должны соответствовать 1-ой клавише, с ( K ₁ + 1) -ого по некоторый K ₂ -ой — 2-ой клавише и т. д., до K _M = N . Конкретные значения K ₁ , K ₂ , ..., K _{M - 1} не задаются — их, наоборот, нужно подобрать.

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