B. Кормен — лучший друг человека
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

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

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

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

Входные данные

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

Во второй строке записаны целые числа a1, a2, ..., an (0 ≤ ai ≤ 500) — количество прогулок Кормена в i-й день, которые уже запланированы Поликарпом.

Выходные данные

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

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

Примеры
Входные данные
3 5
2 0 1
Выходные данные
4
2 3 2
Входные данные
3 1
0 0 0
Выходные данные
1
0 1 0
Входные данные
4 6
2 4 3 5
Выходные данные
0
2 4 3 5