English · Original
Chinese · Translation
Formal · Original
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.
## 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 _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.
## 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.
[samples]
[{"iden":"statement","content":"Polycarp 是餐厅 \"Ber Patio\" 的常客，他喜欢在那里吃午餐。\n\n\"Ber Patio\" 为常客提供特殊的优惠计划：顾客可以累积积分，并用积分部分抵扣餐费。\n\n假设顾客当前有 #cf_span[b] 积分，她需要支付 #cf_span[r] 卢布的午餐费用。在这种情况下，顾客可以使用积分（1 积分 = 1 卢布）来减少付款金额。她最多可以用积分抵扣一半的费用。然而，每支付 10 卢布，就会向她的积分账户中增加 1 积分。\n\n形式化描述如下：\n\n最初，Polycarp 的账户中有 #cf_span[b] 积分。Polycarp 将在接下来的 #cf_span[n] 天内到 \"Ber Patio\" 吃午餐。他估计了序列 #cf_span[a1, a2, ..., an]，其中 #cf_span[ai] 表示第 #cf_span[i] 天的账单金额（以卢布为单位）。所有账单的总和不超过 #cf_span[105] 卢布。\n\n请编写一个程序，找出 Polycarp 所需支付的最少卢布数，以及使用积分的最优策略。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[b]（#cf_span[1 ≤ n ≤ 5000]，#cf_span[0 ≤ b ≤ 105]），分别表示天数和 Polycarp 初始拥有的积分数量。\n\n第二行包含整数序列 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 1000]），其中 #cf_span[ai] 表示第 #cf_span[i] 天账单的卢布金额。\n\n保证所有账单的总和不超过 #cf_span[105] 卢布。\n\n第一行输出 Polycarp 为支付全部 #cf_span[n] 张账单所需支付的最少卢布数。\n\n第二行输出一个整数序列 #cf_span[b1, b2, ..., bn]，其中 #cf_span[bi] 表示第 #cf_span[i] 天使用的积分数量。如果有多个解，输出任意一个即可。"},{"iden":"input","content":"第一行包含两个整数 #cf_span[n] 和 #cf_span[b]（#cf_span[1 ≤ n ≤ 5000]，#cf_span[0 ≤ b ≤ 105]），分别表示天数和 Polycarp 初始拥有的积分数量。第二行包含整数序列 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 1000]），其中 #cf_span[ai] 表示第 #cf_span[i] 天账单的卢布金额。保证所有账单的总和不超过 #cf_span[105] 卢布。"},{"iden":"output","content":"第一行输出 Polycarp 为支付全部 #cf_span[n] 张账单所需支付的最少卢布数。第二行输出一个整数序列 #cf_span[b1, b2, ..., bn]，其中 #cf_span[bi] 表示第 #cf_span[i] 天使用的积分数量。如果有多个解，输出任意一个即可。"},{"iden":"examples","content":"输入\n3 2\n112 75 52\n输出\n110\n2 5 22\n\n输入\n3 39\n58 64 33\n输出\n107\n28 4 16 "}]}
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of days.
Let $ b \in \mathbb{Z}_{\geq 0} $ be the initial bonus balance.
Let $ A = (a_1, a_2, \dots, a_n) $ be the sequence of daily receipt amounts, where $ a_i \in \mathbb{Z}^+ $.
**Constraints**
1. $ 1 \leq n \leq 5000 $
2. $ 0 \leq b \leq 10^5 $
3. $ 1 \leq a_i \leq 1000 $ for all $ i \in \{1, \dots, n\} $
4. $ \sum_{i=1}^n a_i \leq 10^5 $
**Rules**
For each day $ i $:
- Let $ b_i \in \mathbb{Z}_{\geq 0} $ be the number of bonuses used on day $ i $.
- The amount paid in cash is $ c_i = a_i - b_i $.
- Constraints on bonus usage:
$$
0 \leq b_i \leq \left\lfloor \frac{a_i}{2} \right\rfloor, \quad b_i \leq \text{current bonus balance}
$$
- After payment, bonuses are earned:
$$
\text{bonuses gained} = \left\lfloor \frac{c_i}{10} \right\rfloor
$$
- Bonus balance evolves as:
$$
b_{\text{next}} = b_{\text{current}} - b_i + \left\lfloor \frac{c_i}{10} \right\rfloor
$$
**Objective**
Minimize total cash expenditure:
$$
\sum_{i=1}^n c_i = \sum_{i=1}^n (a_i - b_i)
$$
Subject to bonus balance constraints and bonus earning rules.
Output the minimal total cash spent and a valid sequence $ (b_1, b_2, \dots, b_n) $.
API Response (JSON)
{
"problem": {
"name": "F. Ber Patio",
"description": {
"content": "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 partial",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 3000,
"memory_limit": 524288
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF730F"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Polycarp is a regular customer at the restaurant \"Ber Patio\". He likes having lunches there.\n\n\"Ber Patio\" has special discount program for regular customers. A customer can collect bonuses and partial...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "[{\"iden\":\"statement\",\"content\":\"Polycarp 是餐厅 \\\"Ber Patio\\\" 的常客，他喜欢在那里吃午餐。\\n\\n\\\"Ber Patio\\\" 为常客提供特殊的优惠计划：顾客可以累积积分，并用积分部分抵扣餐费。\\n\\n假设顾客当前有 #cf_span[b] 积分，她需要支付 #cf_span[r] 卢布的午餐费用。在这种情况下，顾客可以使用积分（1 积分 = ...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the number of days. \nLet $ b \\in \\mathbb{Z}_{\\geq 0} $ be the initial bonus balance. \nLet $ A = (a_1, a_2, \\dots, a_n) $ be the sequence of daily rece...",
"is_translate": false,
"language": "Formal"
}
]
}