← 返回题目列表

Codeforces · 732/B

B. 科门---男人最好的朋友

中文机器翻译题面 查看原题

最近为波利卡普买了一只狗。这只狗的名字叫科门。现在波利卡普有很多麻烦。例如,科门喜欢散步。

根据Polycarp的经验,狗需要连续两天至少k次散步才能感觉良好。例如,如果 k = 5,昨天 Polycarp 和 Cormen 一起散步了 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) — 任意连续两天与 Cormen 一起散步的天数和最小次数。

第二行包含整数 a1, a2, ..., an (0 ≤ ai ≤ 500) – 波利卡普已计划的第 i 天与 Cormen 一起散步的次数。

输出

在第一行中打印 Polycarp 在接下来的 n 天内应该进行的最少额外步行次数,以便 Cormen 在所有日子里都感觉良好。

在第二行中打印 n 个整数 b1, b2, ..., bn,其中 bi - 根据找到的解决方案在第 i 天步行的总数(对于从 1 到 n 的所有 i,ai ≤ bi)。如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

3 5
2 0 1

输出 #1

4
2 3 2

输入 #2

3 1
0 0 0

输出 #2

1
0 1 0

输入 #3

4 6
2 4 3 5

输出 #3

0
2 4 3 5