Ночь. Неуловимый Джо пробрался внутрь сейфа главного банка страны. Здесь имеется n ячеек, расположенных в ряд, в каждой из которых лежит некоторое количество алмазов. Для удобства пронумеруем ячейки натуральными числами от 1 до n слева направо.

К сожалению, Джо не отключил последнюю из систем безопасности. Зато он знает как она устроена.

Каждую минуту система безопасности определяет для каждых двух соседних ячеек (разность номеров которых ровно 1) суммарное количество алмазов в них. В итоге получается n - 1 сумма. Если хотя бы одна из них отличается от соответствующей суммы, полученной при предыдущем измерении, система безопасности срабатывает.

Джо может перемещать алмазы между проверками системы безопасности. За минуту между двумя проверками он успевает сделать не более m перемещений. Перемещением считается одна из трех следующих операций: перемещение алмаза из любой ячейки в любую другую, перемещение алмаза из любой ячейки в карман Джо, перемещение алмаза из кармана в любую ячейку. Изначально карман Джо пуст, в любую ячейку и в карман помещается неограниченное количество алмазов. Считается, что до всех действий Джо система делает хотя бы одну проверку.

Утром в банк придут банковские служащие, поэтому Джо должен уйти из банка до этого момента. У Джо есть k перерывов между проверками системы безопасности перед тем, как нужно будет скрыться. Все, что останется при этом у Джо в кармане, считается его добычей.

Определите наибольшее количество алмазов, которые может унести с собой Джо. Система безопасности при этом не должна сработать (в том числе и после того, как Джо покинет банк), а скрыться Джо должен до наступления утра.