CF730F.Ber Patio

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 ()),
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 _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 105 burles.

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

波利卡普是餐厅“Ber Patio”的常客，他喜欢在那里吃午餐。

“Ber Patio”为常客提供特别折扣计划：顾客可以累积积分（bonuses），并用积分部分抵扣餐厅消费。

假设某顾客当前拥有 $b$ 个积分，而她某顿午餐需支付 $r$ 卢布（burles）。此时，她可使用积分（1 积分 = 1 卢布）来减少应付金额。但她最多只能用积分抵扣总费用的一半。此外，每实际支付满 10 卢布（向下取整），她将额外获得 1 个积分。

形式化地：

1. 顾客可任选一个积分使用数量 $x$（满足 $0 \le x \le \min(b, \lfloor r/2 \rfloor)$）；
2. 顾客的积分余额减少 $x$；
3. 顾客实际支付 $r - x$ 卢布；
4. 顾客的积分余额增加 $\left\lfloor \dfrac{r - x}{10} \right\rfloor$（即采用向下取整的整数除法）。

初始时，波利卡普账户上有 $b$ 个积分。接下来 $n$ 天，他将在“Ber Patio”用餐。他已预估出每天的账单金额 $a_1, a_2, \dots, a_n$，其中 $a_i$ 表示第 $i$ 天的账单金额（单位：卢布）。所有账单金额之和不超过 $10^5$ 卢布。

请编写程序，计算波利卡普需要支付的最少卢布总额，并给出一种最优的积分使用策略。

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 _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 105 burles.

第一行包含两个整数 $n$ 和 $b$（$1 \leq n \leq 5000$，$0 \leq b \leq 10^5$）—— 分别表示天数以及 Polycarp 初始拥有的奖金数量。

第二行包含一个整数序列 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 1000$），其中 $a_i$ 表示第 $i$ 天收据上的金额（单位：burles）。

保证所有收据金额之和不超过 $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.

第一行输出支付全部 $n$ 张收据所需的最小预期金额（单位：burles）。

第二行输出整数序列 $b_1,\ b_2,\ \dots,\ b_n$，其中 $b_i$ 表示第 $i$ 天使用的积分数量。若存在多种解，输出任意一种即可。