Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tags yet

No tag edit access

F. Ber Patio

time limit per test

3 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputPolycarp 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:

- a customer can choose any number
*x*of bonuses to use ()), - the customer's bonus balance is reduced by
*x*, - the customer pays
*r*-*x*burles, - 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 *a*_{1}, *a*_{2}, ..., *a*_{n}, where *a*_{i} is the number of burles in a receipt for the *i*-th day. The sum over all receipts doesn't exceed 10^{5} 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* ≤ 10^{5}) — number of days and initial number of bonuses Polycarp has.

The second line contains the integer sequence *a*_{1}, *a*_{2}, ..., *a*_{n} (1 ≤ *a*_{i} ≤ 1000), where *a*_{i} is the amount of burles in the *i*-th day's receipt.

It is guaranteed that the sum of all receipts does not exceed 10^{5} 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 *b*_{1}, *b*_{2}, ..., *b*_{n}, where *b*_{i} 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

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/25/2017 03:01:43 (c4).

Desktop version, switch to mobile version.
User lists

Name |
---|