— Хорошая игра, — Принцесса произнесла это немного отстранённо; было понятно, что она думает о чём-то другом.

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

Принцесса А. предложила Рыцарю сыграть с ней в игру с числами. Она записала на листе бумаги число 0. Назовём это число текущим результатом.

Дальнейшие ходы принцессы А. и Рыцаря состоят в следующем. Она называет некоторое целое положительное число, а Рыцарь говорит, что нужно сделать с этим числом: прибавить его к текущему результату или же отнять его из текущего результата.

Принцесса А. выполняет действие, предложенное Рыцарем, и вычисляет полученное значение. Это значение и становится новым текущим результатом.

Принцесса А. желает, чтобы текущий результат всегда был не меньше нуля и не больше k. Игра заканчивается, когда Рыцарь не может сделать очередной ход (т.е. любое действие приводит к выходу за границы указанного диапазона) или же когда принцесса А. исчерпает задуманную ей последовательность из n чисел.

Рыцарю удалось узнать, какую последовательность из n чисел принцесса задумала, и теперь он хочет, чтобы игра продлилась как можно дольше.

Ваша задача — определить максимально возможное количество ходов, которое сможет сделать Рыцарь в игре.