Недавно Поликарпу наконец купили собаку, которую он назвал Корменом. Теперь у Поликарпа появилось так много хлопот! Например, Кормен очень любит прогулки.
Опытным путем Поликарп установил, что псу требуется не менее k прогулок суммарно за любые два последовательных дня, чтобы чувствовать себя отлично. Например, если k = 5 и вчера Поликарп гулял с собакой 2 раза, то сегодня он должен будет погулять не менее 3-х раз.
Поликарп проанализировал все свои дела на ближайшие n дней вперед и составил последовательность из n целых чисел a1, a2, ..., an, где ai — количество прогулок с собакой, которые он совершит в i-й день, исполняя все свои дела во время них (например, ему надо сходить в магазин, выбросить мусор и так далее).
Помогите Поликарпу определить наименьшее количество прогулок сверх намеченных, которые ему нужно совершить за n дней для того, чтобы Кормен чувствовал себя отлично на протяжении всех n дней. Вы можете считать, что в день до первого и в день после n-го Поликарп выгуливал Кормена ровно по k раз.
Напишите программу, которая найдет наименьшее количество дополнительных прогулок и соответствующее расписание — последовательность целых чисел b1, b2, ..., bn (bi ≥ ai), где bi обозначает суммарное количество прогулок в i-й день.
Выходные данные
В первую строку выведите наименьшее дополнительное количество прогулок, которые нужно совершить за n дней для того, чтобы Кормен всегда чувствовал себя отлично.
Во вторую строку выведите n целых чисел b1, b2, ..., bn, где bi — суммарное количество прогулок в i-й день в соответствии с найденным решением (ai ≤ bi для всех i от 1 до n). Если решений несколько, разрешается вывести любое из них.