CF730F.Ber Patio

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.

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.

无