← 返回题目列表

Codeforces · 730/F

F. 贝尔露台

中文机器翻译题面 查看原题

Polycarp 是“Ber Patio”餐厅的常客。他喜欢在那里吃午餐。

“Ber Patio”为老顾客提供特别折扣计划。顾客可以领取奖金并部分支付餐厅的费用。

假设客户当前有 b 奖金,她必须支付 r burles 的午餐费用。在这种情况下,客户可以使用奖金(1 奖金 = 1 burle)来减少付款。她最多可以用奖金支付一半的付款。然而,客户每支付 10 burles,奖金余额中就会增加 1 点奖金。

正式:

1. 客户可以选择使用任意数量 x 的奖金 ($$0 \leq x \leq \min(b, \left\lfloor \frac{r}{2} \right\rfloor)$$)),
2.客户的奖金余额减少x,
3. 客户支付r - x burles,
4. 客户的奖金余额增加⌊(r - x) / 10⌋(即采用整数除法向下取整)。

最初,Polycarp 的账户上有 b 奖金。 Polycarp 将在接下来的 n 天里在“Ber Patio”吃午餐。他估计了值 a1, a2, ..., an,其中 ai 是第 i 天收据中的节数。所有收据的总和不超过 105 伯尔。

编写一个程序来找出 Polycarp 必须花费的最少 burles 数量以及使用奖金的最佳策略。

输入

第一行包含两个整数 n 和 b (1 ≤ n ≤ 5000, 0 ≤ b ≤ 105) — 波利卡普拥有的天数和初始奖金数。

第二行包含整数序列 a1, a2, ..., an (1 ≤ ai ≤ 1000),其中 ai 是第 i 天收据中的字节数。

保证所有收据的总和不超过105 burles。

输出

在第一行,打印支付所有 n 个收据的预期最小数量的 burles。

在第二行,打印整数序列 b1, b2, ..., bn,其中 bi 是第 i 天使用的奖金数量。如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

3 21
12 75 52

输出 #1

110
2 5 22

输入 #2

3 39
58 64 33

输出 #2

107
28 4 16