English · Original
Chinese · Translation
Formal · Original
Recently a dog was bought for Polycarp. The dog's name is Cormen. Now Polycarp has a lot of troubles. For example, Cormen likes going for a walk.
Empirically Polycarp learned that the dog needs at least _k_ walks for any two consecutive days in order to feel good. For example, if _k_ = 5 and yesterday Polycarp went for a walk with Cormen 2 times, today he has to go for a walk at least 3 times.
Polycarp analysed all his affairs over the next _n_ days and made a sequence of _n_ integers _a_1, _a_2, ..., _a__n_, where _a__i_ is the number of times Polycarp will walk with the dog on the _i_\-th day while doing all his affairs (for example, he has to go to a shop, throw out the trash, etc.).
Help Polycarp determine the minimum number of walks he needs to do additionaly in the next _n_ days so that Cormen will feel good during all the _n_ days. You can assume that on the day before the first day and on the day after the _n_\-th day Polycarp will go for a walk with Cormen exactly _k_ times.
Write a program that will find the minumum number of additional walks and the appropriate schedule — the sequence of integers _b_1, _b_2, ..., _b__n_ (_b__i_ ≥ _a__i_), where _b__i_ means the total number of walks with the dog on the _i_\-th day.
## Input
The first line contains two integers _n_ and _k_ (1 ≤ _n_, _k_ ≤ 500) — the number of days and the minimum number of walks with Cormen for any two consecutive days.
The second line contains integers _a_1, _a_2, ..., _a__n_ (0 ≤ _a__i_ ≤ 500) — the number of walks with Cormen on the _i_\-th day which Polycarp has already planned.
## Output
In the first line print the smallest number of additional walks that Polycarp should do during the next _n_ days so that Cormen will feel good during all days.
In the second line print _n_ integers _b_1, _b_2, ..., _b__n_, where _b__i_ — the total number of walks on the _i_\-th day according to the found solutions (_a__i_ ≤ _b__i_ for all _i_ from 1 to _n_). If there are multiple solutions, print any of them.
[samples]
最近，Polycarp 买了一只狗，名字叫 Cormen。现在 Polycarp 遇到了很多麻烦，比如 Cormen 喜欢出去散步。
通过经验，Polycarp 发现，为了使狗感到舒服，任意连续两天的散步次数之和至少为 #cf_span[k]。例如，如果 #cf_span[k = 5]，而昨天 Polycarp 与 Cormen 散步了 #cf_span[2] 次，那么今天他至少需要散步 #cf_span[3] 次。
Polycarp 分析了接下来的 #cf_span[n] 天的所有事务，并生成了一个包含 #cf_span[n] 个整数的序列 #cf_span[a1, a2, ..., an]，其中 #cf_span[ai] 表示 Polycarp 在第 #cf_span[i] 天因处理事务（例如去商店、扔垃圾等）而计划与狗散步的次数。
请帮助 Polycarp 确定在接下来的 #cf_span[n] 天中，他至少需要额外增加多少次散步，才能让 Cormen 在这 #cf_span[n] 天中每天都感到舒服。你可以假设，在第一天之前和第 #cf_span[n] 天之后，Polycarp 都会与 Cormen 散步恰好 #cf_span[k] 次。
编写一个程序，找出最少的额外散步次数以及对应的计划——一个整数序列 #cf_span[b1, b2, ..., bn]（#cf_span[bi ≥ ai]），其中 #cf_span[bi] 表示第 #cf_span[i] 天与狗散步的总次数。
## Input
第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n, k ≤ 500]）——天数和任意连续两天中与 Cormen 散步的最小次数。第二行包含整数 #cf_span[a1, a2, ..., an]（#cf_span[0 ≤ ai ≤ 500]）——Polycarp 已计划的第 #cf_span[i] 天与 Cormen 散步的次数。
## Output
第一行输出 Polycarp 在接下来的 #cf_span[n] 天中为让 Cormen 感到舒服而必须增加的最少散步次数。第二行输出 #cf_span[n] 个整数 #cf_span[b1, b2, ..., bn]，其中 #cf_span[bi] 表示根据所求解法第 #cf_span[i] 天的散步总次数（对所有 #cf_span[i] 从 1 到 #cf_span[n]，满足 #cf_span[ai ≤ bi]）。如果有多个解，输出任意一个即可。
[samples]
**Definitions**
Let $ n, k \in \mathbb{Z}^+ $ with $ 1 \leq n, k \leq 500 $.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of non-negative integers with $ 0 \leq a_i \leq 500 $.
Let $ b_0 = k $, $ b_{n+1} = k $ (virtual days before and after).
**Constraints**
For each $ i \in \{1, \dots, n\} $:
- $ b_i \geq a_i $
- $ b_i + b_{i-1} \geq k $
- $ b_i + b_{i+1} \geq k $
**Objective**
Minimize $ \sum_{i=1}^n (b_i - a_i) $, and output the minimal total additional walks and a sequence $ B = (b_1, \dots, b_n) $ achieving it.
API Response (JSON)
{
"problem": {
"name": "B. Cormen — The Best Friend Of a Man",
"description": {
"content": "Recently a dog was bought for Polycarp. The dog's name is Cormen. Now Polycarp has a lot of troubles. For example, Cormen likes going for a walk. Empirically Polycarp learned that the dog needs at le",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF732B"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Recently a dog was bought for Polycarp. The dog's name is Cormen. Now Polycarp has a lot of troubles. For example, Cormen likes going for a walk.\n\nEmpirically Polycarp learned that the dog needs at le...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "最近，Polycarp 买了一只狗，名字叫 Cormen。现在 Polycarp 遇到了很多麻烦，比如 Cormen 喜欢出去散步。\n\n通过经验，Polycarp 发现，为了使狗感到舒服，任意连续两天的散步次数之和至少为 #cf_span[k]。例如，如果 #cf_span[k = 5]，而昨天 Polycarp 与 Cormen 散步了 #cf_span[2] 次，那么今天他至少需要散步 #cf...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, k \\in \\mathbb{Z}^+ $ with $ 1 \\leq n, k \\leq 500 $. \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of non-negative integers with $ 0 \\leq a_i \\leq 500 $. \nLet $ b_0 = k...",
"is_translate": false,
"language": "Formal"
}
]
}