Problem: Polycarp is a regular customer at the restaurant "Ber Patio". He likes having lunches there.

"Ber Patio" has special discount program for regular customers. A customer can collect bonuses and partially cover expenses in the restaurant.

Let's assume a customer currently has b bonuses and she has to pay r burles for a lunch. In this case the customer can use bonuses (1 bonus = 1 burle) to reduce the payment. She can cover at most half of the payment using bonuses. However, 1 bonus will be added to the customer's bonus balance per each 10 burles she paid.

Formally:

  1. a customer can choose any number x of bonuses to use (<image>)), 
  2. the customer's bonus balance is reduced by x, 
  3. the customer pays r - x burles, 
  4. the customer's bonus balance is increased by ⌊(r - x) / 10⌋ (i.e. integer division rounded down is used). 



Initially, there are b bonuses on Polycarp's account. Polycarp is going to have a lunch in "Ber Patio" for the next n days. He estimated the values a1, a2, ..., an, where ai is the number of burles in a receipt for the i-th day. The sum over all receipts doesn't exceed 105 burles.

Write a program to find the minimum number of burles Polycarp has to spend and an optimal strategy to use bonuses.

Input

The first line contains two integer numbers n and b (1 ≤ n ≤ 5000, 0 ≤ b ≤ 105) — number of days and initial number of bonuses Polycarp has.

The second line contains the integer sequence a1, a2, ..., an (1 ≤ ai ≤ 1000), where ai is the amount of burles in the i-th day's receipt.

It is guaranteed that the sum of all receipts does not exceed 105 burles.

Output

On the first line, print the expected minimal number of burles to pay for all n receipts.

On the second line, print the sequence of integer numbers b1, b2, ..., bn, where bi is the number of bonuses to use on the i-th day. If there are multiple solutions, print any of them.

Examples

Input

3 21
12 75 52


Output

110
2 5 22 


Input

3 39
58 64 33


Output

107
28 4 16 

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
std::uniform_int_distribution<std::mt19937::result_type> udist(0, 1);
std::mt19937 rng;
using namespace std;
FILE *in, *out;
int ri() {
  int a;
  fscanf(in, "%d", &a);
  return a;
}
double rf() {
  double a;
  fscanf(in, "%lf", &a);
  return a;
}
char sbuf[100005];
string rstr() {
  char c;
  char *b = sbuf;
  while (c = fgetc(in)) {
    if (c == '\n' || c == 255) break;
    *b++ = c;
  }
  *b = 0;
  return sbuf;
}
long long nod(long long a, long long b) {
  if (a == 1 || b == 1) return 1;
  if (a == 0) return b;
  if (b == 0) return a;
  return nod(b % a, a);
}
vector<int> primes;
void calculatePrimes() {
  primes.push_back(2);
  for (int i = 3; i < 500000; i += 2) {
    bool bFound = false;
    int m = (int)sqrt((float)i);
    for (int j = 1; j < primes.size() && !bFound && primes[j] <= m; j++)
      bFound = ((i % primes[j]) == 0);
    if (!bFound) primes.push_back(i);
  }
}
void egcd(int a, int b, int &g, int &x, int &y) {
  if (a == 0) {
    g = b;
    x = 0;
    y = 1;
    return;
  }
  egcd(b % a, a, g, y, x);
  x = x - (b / a) * y;
}
int modinv(int a, int m) {
  int g = 0, x = 0, y = 0;
  egcd(a, m, g, x, y);
  return (x + m) % m;
}
struct Var {
  int nd;
  long long ms;
  long long ks;
  int ku;
  bool operator<(const Var &r) const {
    if (r.ku < ku) return false;
    if (r.ku > ku) return true;
    if (r.ms < ms) return true;
    if (r.ms > ms) return false;
    return r.ks < ks;
  }
};
int main() {
  rng.seed(time(NULL));
  long long n, b;
  cin >> n >> b;
  vector<long long> a(n);
  vector<long long> bp(n);
  for (int i = (0); i < (((n))); ++i) {
    cin >> a[i];
    bp[i] = 0;
  }
  long long sb = b;
  for (long long i = 0; i < n; i++) {
    bp[i] = min(b, a[i] % 10);
    if (bp[i] > a[i] / 2) bp[i] = a[i] / 2;
    b -= bp[i];
    b += (a[i] - bp[i]) / 10;
  }
  long long sr = 0;
  for (long long i = n - 1; i >= 0; i--) {
    b -= (a[i] - bp[i]) / 10;
    sr -= (a[i] - bp[i]) / 10;
    if (b - sr < 20) sr = sr;
    long long ch = (a[i] / 2 - bp[i]) / 10 * 10;
    if (sr >= 0)
      ch = min((b - sr) / 11 * 10, ch);
    else
      ch = min(b / 10 * 10, ch);
    if (ch > 0) {
      bp[i] += ch;
      b -= ch;
      sr += ch / 10;
    }
    if (sr < 0) sr = 0;
    sr += bp[i];
    b += bp[i];
  }
  long long sum = 0;
  for (int i = (0); i < (((n))); ++i) sum += a[i] - bp[i];
  for (long long j = 10; j >= 1; j--) {
    b = sb;
    long long b1 = sb;
    long long t1, t2;
    t1 = t2 = 0;
    long long d1, d2;
    d1 = d2 = 0;
    long long nb = 0;
    long long ne1 = 0;
    long long ne2 = 0;
    for (long long i = 0; i < n; i++) {
      b -= bp[i];
      if (b < 0) nb++;
      b += (a[i] - bp[i]) / 10;
      t1 += (a[i] - bp[i]) / 10;
      d1 += a[i] - bp[i];
      if (bp[i] != 0) nb++;
      if (t1 < t2) nb++;
      if ((a[i] - bp[i]) % 10 != 0) ne1 += (a[i] - bp[i]) % 10;
      if ((d1 - ne1) != t1 * 10) nb++;
    }
    sr = 0;
    for (long long i = n - 1; i >= 0; i--) {
      b -= (a[i] - bp[i]) / 10;
      sr -= (a[i] - bp[i]) / 10;
      if (bp[i] != 0 || a[i] % 10 == 0) {
        long long ch = (a[i] / 2 - bp[i]);
        if (sr >= 0)
          ch = min(b - sr - 1, ch);
        else
          ch = min(b, ch);
        if (ch == j) {
          bp[i] += ch;
          b -= ch;
          sr++;
        }
      } else {
        long long ch = min(b - max(sr, (long long)0), (a[i] / 2 - bp[i]));
        bp[i] += ch;
        b -= ch;
      }
      if (sr < 0) sr = 0;
      sr += bp[i];
      b += bp[i];
    }
  }
  sum = 0;
  long long sum1 = 0;
  for (int i = (0); i < (((n))); ++i) {
    sum += a[i] - bp[i];
  }
  cout << sum << endl;
  for (int i = (0); i < (((n))); ++i) cout << bp[i] << " ";
  return 0;
}