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>
using namespace std;
const int N = 5555 + 10;
const long long INF = 1e9 + 19;
int n, B;
int a[N];
int b[N];
int add[N];
int can[N];
void read() {
  scanf("%d%d", &n, &B);
  for (int i = 0; i < n; i++) scanf("%d", &a[i]);
}
bool isGood() {
  int curB = B;
  for (int i = 0; i < n; i++) {
    assert(b[i] * 2 <= a[i]);
    if (curB < b[i]) return 0;
    curB -= b[i];
    curB += (a[i] - b[i]) / 10;
  }
  return 1;
}
void build() {
  for (int i = n - 1; i >= 0; i--) {
    b[i] += add[i];
    if (!isGood()) {
      b[i] -= add[i];
      for (int j = 1;; j++) {
        b[i]++;
        if (!isGood()) {
          b[i]--;
          break;
        }
      }
      break;
    }
  }
  for (int val = 10; val >= 1; val--) {
    for (int i = n - 1; i >= 0; i--) {
      bool fail = 0;
      while (true) {
        int rem = can[i] - b[i];
        if (rem >= val) {
          b[i] += val;
          if (!isGood()) {
            b[i] -= val;
            fail = 1;
            break;
          }
        } else
          break;
      }
      if (val < 10 && fail) {
        break;
      }
    }
  }
}
int solve() {
  for (int i = 0; i < n; i++) b[i] = 0;
  for (int i = 0; i < n; i++) can[i] = a[i] / 2;
  for (int i = 0; i < n; i++) add[i] = min(can[i], a[i] % 10);
  add[n - 1] = can[n - 1];
  build();
  int sum = 0;
  for (int i = 0; i < n; i++) sum += a[i] - b[i];
  assert(isGood());
  printf("%d\n", sum);
  for (int i = 0; i < n; i++) printf("%d ", b[i]);
  puts("");
  return sum;
}
void genTest() {
  n = 5000;
  int T = 40;
  B = rand() % T;
  for (int i = 0; i < n; i++) a[i] = rand() % T + 1;
}
int stupid() {
  int mx = B;
  for (int i = 0; i < n; i++) mx += a[i];
  vector<vector<int>> dp(n + 1, vector<int>(mx + 1, INF));
  dp[0][B] = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j <= mx; j++) {
      if (dp[i][j] < INF) {
        for (int k = 0; k <= min(j, a[i] / 2); k++) {
          int newB = j - k + (a[i] - k) / 10;
          dp[i + 1][newB] = min(dp[i + 1][newB], dp[i][j] + a[i] - k);
        }
      }
    }
  }
  int answer = INF;
  for (int k = 0; k <= mx; k++) answer = min(answer, dp[n][k]);
  return answer;
}
void printTest() {
  cout << n << " " << B << endl;
  for (int i = 0; i < n; i++) cout << a[i] << " ";
  cout << endl;
}
void stress() {
  for (int tt = 0;; tt++) {
    cerr << "tt"
         << " = " << tt << endl;
    genTest();
    printTest();
    exit(0);
    int r1 = solve();
    int r2 = stupid();
    if (r1 != r2) {
      cerr << "("
           << "r1"
           << ", "
           << "r2"
           << ") = (" << r1 << ", " << r2 << ")\n";
      ;
    }
    assert(r1 == r2);
  }
}
int main() {
  if (1) {
    int k = 1;
    for (int tt = 0; tt < k; tt++) {
      read();
      solve();
    }
  } else {
    stress();
  }
  return 0;
}