{"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 partially cover expenses in the restaurant.\n\nLet'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.\n\nFormally:\n\n1.  a customer can choose any number _x_ of bonuses to use ()),\n2.  the customer's bonus balance is reduced by _x_,\n3.  the customer pays _r_ - _x_ burles,\n4.  the customer's bonus balance is increased by ⌊(_r_ - _x_) / 10⌋ (i.e. integer division rounded down is used).\n\nInitially, 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.\n\nWrite a program to find the minimum number of burles Polycarp has to spend and an optimal strategy to use bonuses.\n\n## Input\n\nThe 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.\n\nThe 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.\n\nIt is guaranteed that the sum of all receipts does not exceed 105 burles.\n\n## Output\n\nOn the first line, print the expected minimal number of burles to pay for all _n_ receipts.\n\nOn 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\n[samples]","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 积分 = 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 \"}]}","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 receipt amounts, where $ a_i \\in \\mathbb{Z}^+ $.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 5000 $  \n2. $ 0 \\leq b \\leq 10^5 $  \n3. $ 1 \\leq a_i \\leq 1000 $ for all $ i \\in \\{1, \\dots, n\\} $  \n4. $ \\sum_{i=1}^n a_i \\leq 10^5 $  \n\n**Rules**  \nFor each day $ i $:  \n- Let $ b_i \\in \\mathbb{Z}_{\\geq 0} $ be the number of bonuses used on day $ i $.  \n- The amount paid in cash is $ c_i = a_i - b_i $.  \n- Constraints on bonus usage:  \n  $$\n  0 \\leq b_i \\leq \\left\\lfloor \\frac{a_i}{2} \\right\\rfloor, \\quad b_i \\leq \\text{current bonus balance}\n  $$  \n- After payment, bonuses are earned:  \n  $$\n  \\text{bonuses gained} = \\left\\lfloor \\frac{c_i}{10} \\right\\rfloor\n  $$  \n- Bonus balance evolves as:  \n  $$\n  b_{\\text{next}} = b_{\\text{current}} - b_i + \\left\\lfloor \\frac{c_i}{10} \\right\\rfloor\n  $$  \n\n**Objective**  \nMinimize total cash expenditure:  \n$$\n\\sum_{i=1}^n c_i = \\sum_{i=1}^n (a_i - b_i)\n$$  \nSubject to bonus balance constraints and bonus earning rules.  \nOutput the minimal total cash spent and a valid sequence $ (b_1, b_2, \\dots, b_n) $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF730F","tags":[],"sample_group":[["3 21\n12 75 52","110\n2 5 22"],["3 39\n58 64 33","107\n28 4 16"]],"created_at":"2026-03-03 11:00:39"}}