Решение задачи Кормен — лучший друг человека с Codeforces

Недавно Поликарпу наконец купили собаку, которую он назвал Корменом. Теперь у Поликарпа появилось так много хлопот! Например, Кормен очень любит прогулки.

Опытным путем Поликарп установил, что псу требуется не менее k прогулок суммарно за любые два последовательных дня, чтобы чувствовать себя отлично. Например, если k = 5 и вчера Поликарп гулял с собакой 2 раза, то сегодня он должен будет погулять не менее 3-х раз.

Поликарп проанализировал все свои дела на ближайшие n дней вперед и составил последовательность из n целых чисел a1, a2, ..., an, где ai — количество прогулок с собакой, которые он совершит в i-й день, исполняя все свои дела во время них (например, ему надо сходить в магазин, выбросить мусор и так далее).

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

Напишите программу, которая найдет наименьшее количество дополнительных прогулок и соответствующее расписание — последовательность целых чисел b1, b2, ..., bn (bi ≥ ai), где bi обозначает суммарное количество прогулок в i-й день.