CodeForces 732B Cormen ¡ª The Best Friend Of a Man

B. Cormen ¡ª The Best Friend Of a Man

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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?=?5and 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?a1,?a2,?...,?an, where?ai?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 integersb1,?b2,?...,?bn?(bi?¡Ý?ai), where?bi?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?a1,?a2,?...,?an?(0?¡Ü?ai?¡Ü?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?b1,?b2,?...,?bn, where?bi?¡ª the total number of walks on the?i-th day according to the found solutions (ai?¡Ü?bi?for all?i?from 1 to?n). If there are multiple solutions, print any of them.

Examples

input

3 5
2 0 1

output

4
2 3 2

input

3 1
0 0 0

output

1
0 1 0

input

4 6
2 4 3 5

output

0
2 4 3 5

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <algorithm>
#include <math.h>

using namespace std;
int n,k;
int a[505];
int b[505];
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    int ans=0;
    for(int i=2;i<=n;i++)
    {
        if(a[i]+a[i-1]>=k) continue;
        else
        {
             ans+=(k-a[i]-a[i-1]);
              a[i]+=(k-a[i]-a[i-1]);
        }


    }
    printf("%d\n",ans);
    for(int i=1;i<=n;i++)
    {
        if(i!=n)
            printf("%d ",a[i]);
        else
            printf("%d\n",a[i]);
    }
    return 0;

}