{"problem":{"name":"C. Robbery","description":{"content":"It is nighttime and Joe the Elusive got into the country's main bank's safe. The safe has _n_ cells positioned in a row, each of them contains some amount of diamonds. Let's make the problem more comf","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF90C"},"statements":[{"statement_type":"Markdown","content":"It is nighttime and Joe the Elusive got into the country's main bank's safe. The safe has _n_ cells positioned in a row, each of them contains some amount of diamonds. Let's make the problem more comfortable to work with and mark the cells with positive numbers from 1 to _n_ from the left to the right.\n\nUnfortunately, Joe didn't switch the last security system off. On the plus side, he knows the way it works.\n\nEvery minute the security system calculates the total amount of diamonds for each two adjacent cells (for the cells between whose numbers difference equals 1). As a result of this check we get an _n_ - 1 sums. If at least one of the sums differs from the corresponding sum received during the previous check, then the security system is triggered.\n\nJoe can move the diamonds from one cell to another between the security system's checks. He manages to move them no more than _m_ times between two checks. One of the three following operations is regarded as moving a diamond: moving a diamond from any cell to any other one, moving a diamond from any cell to Joe's pocket, moving a diamond from Joe's pocket to any cell. Initially Joe's pocket is empty, and it can carry an unlimited amount of diamonds. It is considered that before all Joe's actions the system performs at least one check.\n\nIn the morning the bank employees will come, which is why Joe has to leave the bank before that moment. Joe has only _k_ minutes left before morning, and on each of these _k_ minutes he can perform no more than _m_ operations. All that remains in Joe's pocket, is considered his loot.\n\nCalculate the largest amount of diamonds Joe can carry with him. Don't forget that the security system shouldn't be triggered (even after Joe leaves the bank) and Joe should leave before morning.\n\n## Input\n\nThe first line contains integers _n_, _m_ and _k_ (1 ≤ _n_ ≤ 104, 1 ≤ _m_, _k_ ≤ 109). The next line contains _n_ numbers. The _i_\\-th number is equal to the amount of diamonds in the _i_\\-th cell — it is an integer from 0 to 105.\n\n## Output\n\nPrint a single number — the maximum number of diamonds Joe can steal.\n\n[samples]\n\n## Note\n\nIn the second sample Joe can act like this:\n\nThe diamonds' initial positions are 4 1 3.\n\nDuring the first period of time Joe moves a diamond from the 1\\-th cell to the 2\\-th one and a diamond from the 3\\-th cell to his pocket.\n\nBy the end of the first period the diamonds' positions are 3 2 2. The check finds no difference and the security system doesn't go off.\n\nDuring the second period Joe moves a diamond from the 3\\-rd cell to the 2\\-nd one and puts a diamond from the 1\\-st cell to his pocket.\n\nBy the end of the second period the diamonds' positions are 2 3 1. The check finds no difference again and the security system doesn't go off.\n\nNow Joe leaves with 2 diamonds in his pocket.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"现在是夜晚，狡猾的乔潜入了国家银行的金库。金库中有 #cf_span[n] 个格子排成一行，每个格子中都有一些钻石。为了便于处理，我们将格子从左到右用正整数 #cf_span[1] 到 #cf_span[n] 编号。\n\n不幸的是，乔没有关闭最后一个安保系统。但幸运的是，他知道它的运作方式。\n\n每分钟，安保系统会计算每两个相邻格子中钻石的总和（即编号差为 #cf_span[1] 的格子对）。经过检查后，我们会得到 #cf_span[n - 1] 个和值。如果至少有一个和值与上一次检查得到的对应和值不同，则安保系统会被触发。\n\n乔可以在两次检查之间将钻石从一个格子移动到另一个格子。他在两次检查之间最多能进行 #cf_span[m] 次移动。一次移动操作包括以下三种之一：将一颗钻石从任意格子移动到任意其他格子，将一颗钻石从任意格子移动到乔的口袋，或将一颗钻石从乔的口袋移动到任意格子。初始时乔的口袋是空的，但可以容纳无限多的钻石。我们认为，在乔采取任何行动之前，系统已经至少进行过一次检查。\n\n早晨银行员工会到来，因此乔必须在那之前离开银行。乔离早晨只剩 #cf_span[k] 分钟，每分钟他最多能进行 #cf_span[m] 次操作。最终留在乔口袋中的所有钻石都算作他的战利品。\n\n请计算乔能带走的最大钻石数量。请记住，安保系统不能被触发（即使在乔离开银行后也不能触发），且乔必须在早晨前离开。\n\n第一行包含整数 #cf_span[n], #cf_span[m] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 104], #cf_span[1 ≤ m, k ≤ 109]）。第二行包含 #cf_span[n] 个数字，第 #cf_span[i] 个数字表示第 #cf_span[i] 个格子中的钻石数量，其值为 #cf_span[0] 到 #cf_span[105] 之间的整数。\n\n输出一个数字——乔能偷走的最大钻石数量。\n\n## Input\n\n第一行包含整数 #cf_span[n], #cf_span[m] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 104], #cf_span[1 ≤ m, k ≤ 109]）。第二行包含 #cf_span[n] 个数字，第 #cf_span[i] 个数字表示第 #cf_span[i] 个格子中的钻石数量，其值为 #cf_span[0] 到 #cf_span[105] 之间的整数。\n\n## Output\n\n输出一个数字——乔能偷走的最大钻石数量。\n\n[samples]\n\n## Note\n\n在第二个样例中，乔可以这样操作：\n\n钻石的初始位置为 #cf_span[4] #cf_span[1] #cf_span[3]。\n\n在第一个时间段内，乔将一颗钻石从第 #cf_span[1] 个格子移动到第 #cf_span[2] 个格子，并将一颗钻石从第 #cf_span[3] 个格子放入自己的口袋。\n\n第一个时间段结束时，钻石的位置为 #cf_span[3] #cf_span[2] #cf_span[2]。检查发现无差异，安保系统未触发。\n\n在第二个时间段内，乔将一颗钻石从第 #cf_span[3] 个格子移动到第 #cf_span[2] 个格子，并将一颗钻石从第 #cf_span[1] 个格子放入自己的口袋。\n\n第二个时间段结束时，钻石的位置为 #cf_span[2] #cf_span[3] #cf_span[1]。检查再次发现无差异，安保系统未触发。\n\n现在乔带着 #cf_span[2] 颗钻石离开了。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Let $ a = (a_1, a_2, \\dots, a_n) $ be the initial vector of diamond counts in the $ n $ cells.\n\nDefine the **adjacent sum vector** $ s = (s_1, s_2, \\dots, s_{n-1}) $, where $ s_i = a_i + a_{i+1} $.\n\nJoe may perform up to $ m $ diamond-moving operations per minute for $ k $ minutes, for a total of at most $ mk $ operations.\n\nEach operation is one of:\n- Move a diamond from cell $ i $ to cell $ j $,\n- Move a diamond from cell $ i $ to Joe’s pocket,\n- Move a diamond from Joe’s pocket to cell $ i $.\n\nLet $ b = (b_1, b_2, \\dots, b_n) $ be the final configuration after all operations.\n\n**Constraint:** The adjacent sum vector must remain unchanged:\n$$\nb_i + b_{i+1} = a_i + a_{i+1} \\quad \\text{for all } i = 1, 2, \\dots, n-1.\n$$\n\nLet $ T $ be the total number of diamonds Joe steals:  \n$$\nT = \\sum_{i=1}^n a_i - \\sum_{i=1}^n b_i.\n$$\n\n**Objective:** Maximize $ T $, subject to:\n- $ b_i + b_{i+1} = a_i + a_{i+1} $ for all $ i \\in \\{1, \\dots, n-1\\} $,\n- $ b_i \\in \\mathbb{Z}_{\\geq 0} $ for all $ i $,\n- The total number of diamond movements (i.e., net changes in cell contents, counting both additions and removals) is at most $ mk $.\n\n---\n\n### Key Insight:\n\nThe constraint $ b_i + b_{i+1} = a_i + a_{i+1} $ for all $ i $ implies that the vector $ b $ is **completely determined** by $ b_1 $, via recurrence:\n\n$$\nb_2 = (a_1 + a_2) - b_1, \\\\\nb_3 = (a_2 + a_3) - b_2 = (a_2 + a_3) - [(a_1 + a_2) - b_1] = b_1 + (a_3 - a_1), \\\\\nb_4 = (a_3 + a_4) - b_3 = (a_3 + a_4) - [b_1 + a_3 - a_1] = (a_4 + a_1) - b_1, \\\\\n\\text{and so on.}\n$$\n\nIn general, for all $ i $, $ b_i $ is an affine function of $ b_1 $:\n\n$$\nb_i = \n\\begin{cases}\nb_1 + c_i & \\text{if } i \\text{ odd}, \\\\\nd_i - b_1 & \\text{if } i \\text{ even},\n\\end{cases}\n$$\n\nwhere $ c_i, d_i $ are constants derived from the initial $ a_j $'s.\n\nThus, the entire vector $ b $ is parameterized by a single variable $ x = b_1 \\in \\mathbb{Z}_{\\geq 0} $, and the rest are determined.\n\nMoreover, all $ b_i \\geq 0 $, so $ x $ must lie in a closed interval $ [L, U] \\subset \\mathbb{Z} $, defined by the non-negativity constraints on all $ b_i $.\n\nLet $ S = \\sum_{i=1}^n a_i $, and $ B(x) = \\sum_{i=1}^n b_i(x) $. Then the stolen amount is:\n\n$$\nT(x) = S - B(x)\n$$\n\nWe wish to **maximize** $ T(x) $, i.e., **minimize** $ B(x) $, over $ x \\in [L, U] \\cap \\mathbb{Z} $.\n\nBut we are also constrained by the **total number of operations** needed to transform $ a $ into $ b(x) $.\n\nLet $ d_i = |b_i - a_i| $. The total number of operations required is **not** $ \\sum |b_i - a_i| $, because:\n\n- Moving a diamond from cell $ i $ to cell $ j $ counts as **one** operation, and reduces both $ a_i $ and increases $ a_j $.\n- So the **minimum number of operations** needed to transform $ a $ to $ b $ is equal to the **total net outflow** from all cells, which is:\n\n$$\n\\text{Operations}(a \\to b) = \\sum_{i: b_i < a_i} (a_i - b_i) = \\sum_{i: b_i > a_i} (b_i - a_i)\n$$\n\nBecause every diamond moved out of a cell must be moved into another or into Joe’s pocket, and vice versa.\n\nThus, the number of operations required is exactly the **total amount of diamonds removed from cells** (i.e., the sum of decreases), which equals the **total amount stolen plus the total amount moved between cells**.\n\nBut since diamonds moved between cells do not contribute to Joe’s loot, to **maximize loot**, we want to **minimize** the number of diamonds moved between cells, and **maximize** the number moved directly to Joe’s pocket.\n\nIn fact, the **minimum number of operations** required to achieve configuration $ b $ from $ a $ is:\n\n$$\n\\text{Ops}(a \\to b) = \\sum_{i=1}^n \\max(0, a_i - b_i)\n$$\n\nWhy? Because:\n\n- Every diamond that is **removed** from a cell (i.e., $ a_i - b_i > 0 $) must be moved either to another cell or to Joe’s pocket.\n- But if we are allowed to move diamonds **directly to Joe’s pocket**, then we can avoid moving diamonds between cells entirely — we can just remove $ a_i - b_i $ diamonds from cell $ i $ and put them in Joe’s pocket, in $ a_i - b_i $ operations.\n- Conversely, if $ b_i > a_i $, we must add $ b_i - a_i $ diamonds to cell $ i $, which must come from Joe’s pocket, costing $ b_i - a_i $ operations.\n\nSo total operations:\n\n$$\n\\text{Ops}(a \\to b) = \\sum_{i=1}^n |a_i - b_i| / 2? \\quad \\text{No!}\n$$\n\nWait — correction:\n\nEach operation moves **one diamond**. If we move a diamond from cell $ i $ to cell $ j $, that’s one operation, and it reduces $ a_i $ by 1 and increases $ a_j $ by 1.\n\nIf we move from cell $ i $ to pocket, it reduces $ a_i $ by 1, increases pocket by 1.\n\nSo the **total number of operations** needed to reach $ b $ from $ a $ is:\n\n$$\n\\sum_{i=1}^n \\max(0, a_i - b_i) + \\sum_{i=1}^n \\max(0, b_i - a_i) = \\sum_{i=1}^n |a_i - b_i|\n$$\n\nWait — **no!** That would be true if each change required an independent operation, but moving a diamond from cell $ i $ to cell $ j $ changes both $ a_i $ and $ a_j $ in one operation.\n\nSo the **minimum number of operations** is **not** $ \\sum |a_i - b_i| $, but rather:\n\nLet $ D^+ = \\sum_{i: b_i > a_i} (b_i - a_i) $ — total diamonds to be added to cells  \nLet $ D^- = \\sum_{i: b_i < a_i} (a_i - b_i) $ — total diamonds to be removed from cells\n\nThen, we can move up to $ \\min(D^+, D^-) $ diamonds from overfilled cells to underfilled cells, each such move counts as 1 operation and reduces both $ D^+ $ and $ D^- $ by 1.\n\nThe remaining diamonds must be moved to/from Joe’s pocket:  \n- $ D^- - \\min(D^+, D^-) = \\max(0, D^- - D^+) $ diamonds are stolen (put in pocket)  \n- $ D^+ - \\min(D^+, D^-) = \\max(0, D^+ - D^-) $ diamonds are added from pocket\n\nBut Joe’s **loot** is exactly the amount stolen: $ T = D^- - \\min(D^+, D^-) $\n\nAnd the total number of operations is:\n\n$$\n\\min(D^+, D^-) + (D^- - \\min(D^+, D^-)) + (D^+ - \\min(D^+, D^-)) = D^+ + D^-\n$$\n\nWait — that’s just $ \\sum |a_i - b_i| $\n\nBut that can’t be: if we move a diamond from cell 1 to cell 2, we reduce $ |a_1 - b_1| $ by 1 and $ |a_2 - b_2| $ by 1, but only use 1 operation.\n\nSo the total number of operations is **not** $ \\sum |a_i - b_i| $, but rather:\n\nLet $ \\Delta_i = b_i - a_i $\n\nThen total operations = $ \\sum_{i: \\Delta_i > 0} \\Delta_i + \\sum_{i: \\Delta_i < 0} (-\\Delta_i) - \\text{saved by internal transfers} $\n\nActually, the **minimum number of operations** to transform $ a $ to $ b $ is:\n\n$$\n\\text{Ops}(a \\to b) = \\sum_{i=1}^n \\max(0, a_i - b_i)\n$$\n\n**Why?** Because:\n\n- Every diamond that is removed from a cell must be moved in an operation (either to another cell or to pocket).\n- Every diamond added to a cell must come from an operation (from pocket or another cell).\n- But if we move a diamond from a cell with excess to a cell with deficit, that one operation satisfies both a removal and an addition.\n\nSo the **minimum number of operations** is the **total amount of diamonds that must leave the system** (i.e., go to Joe’s pocket) **plus** the total amount of diamonds that are moved between cells.\n\nBut since we can move diamonds between cells freely, the **minimum number of operations** required is:\n\n$$\n\\text{Ops}(a \\to b) = \\sum_{i=1}^n \\max(0, a_i - b_i)\n$$\n\n**Proof sketch:**  \n- We can always move diamonds directly from overfilled cells to Joe’s pocket: that takes $ \\sum \\max(0, a_i - b_i) $ operations.\n- We can also move diamonds from overfilled to underfilled cells, but that doesn’t reduce the number of operations below the total outflow — because every diamond that leaves a cell must be moved in an operation, regardless of destination.\n- The key is: **each operation removes exactly one diamond from a cell** (if going to pocket or another cell), and **adds one diamond to a cell** (if coming from pocket or another cell).\n- So the number of operations is equal to the total number of diamonds removed from cells, which is $ \\sum \\max(0, a_i - b_i) $, **because** every diamond that ends up in Joe’s pocket was removed from a cell, and every diamond that moves between cells was removed from one cell and added to another — so the number of removals equals the number of additions, and each operation accounts for one removal.\n\nThus, **minimum operations** to reach configuration $ b $ is:\n\n$$\n\\text{Ops}(a \\to b) = \\sum_{i=1}^n \\max(0, a_i - b_i)\n$$\n\nAnd Joe’s loot is:\n\n$$\nT = \\sum_{i=1}^n a_i - \\sum_{i=1}^n b_i = \\sum_{i=1}^n (a_i - b_i) = \\sum_{i=1}^n \\max(0, a_i - b_i) - \\sum_{i=1}^n \\max(0, b_i - a_i)\n$$\n\nBut since $ \\sum (a_i - b_i) = T $, and $ \\sum \\max(0, a_i - b_i) - \\sum \\max(0, b_i - a_i) = T $, we have:\n\nLet $ R = \\sum \\max(0, a_i - b_i) $, $ A = \\sum \\max(0, b_i - a_i) $, then $ T = R - A $, and $ \\text{Ops} = R $.\n\nBut also, since $ \\sum (a_i - b_i) = T $, and $ R - A = T $, then $ A = R - T $, so $ \\text{Ops} = R = T + A \\geq T $.\n\nBut we can choose $ b $ to minimize $ \\text{Ops} $ for a given $ T $, or maximize $ T $ for a given $ \\text{Ops} \\leq mk $.\n\nWe want to **maximize $ T $** subject to $ \\text{Ops}(a \\to b) \\leq mk $, and $ b $ satisfying the adjacent sum constraints.\n\nBut from above, $ \\text{Ops}(a \\to b) = \\sum \\max(0, a_i - b_i) $, and $ T = \\sum (a_i - b_i) $.\n\nSo $ T = \\sum (a_i - b_i) = \\sum \\max(0, a_i - b_i) - \\sum \\max(0, b_i - a_i) = \\text{Ops} - A \\leq \\text{Ops} $\n\nThus, $ T \\leq \\text{Ops} \\leq mk $, so **maximum possible loot is at most $ mk $**.\n\nBut we are constrained by the adjacent sum invariants.\n\nSo the problem reduces to:\n\n> Among all vectors $ b \\in \\mathbb{Z}_{\\geq 0}^n $ such that $ b_i + b_{i+1} = a_i + a_{i+1} $ for all $ i $, maximize $ T = \\sum (a_i - b_i) $, subject to $ \\sum \\max(0, a_i - b_i) \\leq mk $.\n\nBut since $ T = \\sum (a_i - b_i) $, and $ b_i $ is determined by $ b_1 = x $, we can express $ T $ as a linear function of $ x $, and $ \\sum \\max(0, a_i - b_i(x)) $ as a piecewise linear convex function of $ x $.\n\nSo:\n\n### Final Formalization:\n\nLet $ a = (a_1, \\dots, a_n) \\in \\mathbb{Z}_{\\geq 0}^n $ be given.\n\nDefine the sequence $ b(x) = (b_1(x), \\dots, b_n(x)) $, where $ b_1(x) = x $, and for $ i \\geq 2 $:\n\n$$\nb_i(x) = \n\\begin{cases}\nx + c_i & \\text{if } i \\text{ odd}, \\\\\nd_i - x & \\text{if } i \\text{ even},\n\\end{cases}\n$$\n\nwhere $ c_i, d_i $ are constants derived from $ a $, such that $ b_i(x) + b_{i+1}(x) = a_i + a_{i+1} $.\n\nLet $ L = \\max_{i} \\left( \\max(0, \\lceil -c_i \\rceil) \\text{ if } i \\text{ odd}, \\lceil d_i \\rceil \\text{ if } i \\text{ even} \\right) $ — wait, better:\n\nConstraints: $ b_i(x) \\geq 0 $ for all $ i $.\n\nSo:\n\n- For odd $ i $: $ x + c_i \\geq 0 \\Rightarrow x \\geq -c_i $\n- For even $ i $: $ d_i - x \\geq 0 \\Rightarrow x \\leq d_i $\n\nThus, $ x \\in [L, U] $, where:\n\n$$\nL = \\max_{i \\text{ odd}} (-c_i), \\quad U = \\min_{i \\text{ even}} d_i\n$$\n\nLet $ T(x) = \\sum_{i=1}^n (a_i - b_i(x)) $\n\nThis is linear in $ x $: $ T(x) = C - D \\cdot x $, for some constants $ C, D $ (depending on parity of $ n $).\n\nWe want to **maximize** $ T(x) $, i.e., **minimize** $ x $, over $ x \\in [L, U] \\cap \\mathbb{Z} $, **subject to**:\n\n$$\n\\sum_{i=1}^n \\max(0, a_i - b_i(x)) \\leq mk\n$$\n\nLet $ R(x) = \\sum_{i=1}^n \\max(0, a_i - b_i(x)) $\n\nWe want:\n\n$$\n\\max_{x \\in [L, U] \\cap \\mathbb{Z}} T(x) \\quad \\text{subject to} \\quad R(x) \\leq mk\n$$\n\nSince $ T(x) $ is linear and decreasing in $ x $, and $ R(x) $ is piecewise linear and convex (as sum of max-of-linear functions), the feasible set is an interval of integers, and the maximum $ T(x) $ occurs at the **smallest feasible** $ x $.\n\nThus, the solution is:\n\n> Find the smallest integer $ x \\in [L, U] $ such that $ R(x) \\leq mk $, then output $ T(x) = \\sum (a_i - b_i(x)) $.\n\nIf no such $ x $ exists, output 0 (though problem guarantees at least one valid configuration).\n\n---\n\n### Final Answer (Formal Statement):\n\nLet $ a \\in \\mathbb{Z}_{\\geq 0}^n $, $ m, k \\in \\mathbb{Z}_{>0} $.\n\nDefine $ b_1 = x \\in \\mathbb{Z} $, and recursively define $ b_i $ for $ i = 2 $ to $ n $ via:\n\n$$\nb_i = (a_{i-1} + a_i) - b_{i-1}\n$$\n\nLet $ L = \\max_{i \\in \\{1,\\dots,n\\}} \\left( \\max_{\\substack{j \\leq i \\\\ j \\text{ odd}}} \\left( -\\left( \\sum_{\\ell=1}^{j-1} (-1)^{\\ell} (a_\\ell + a_{\\ell+1}) \\right) \\right), \\quad \\min_{\\substack{j \\leq n \\\\ j \\text{ even}}} \\left( \\sum_{\\ell=1}^{j-1} (-1)^{\\ell} (a_\\ell + a_{\\ell+1}) \\right) \\right) $ — too messy.\n\nBetter: Compute $ b_i(x) $ explicitly as:\n\nLet $ s_i = a_i + a_{i+1} $ for $ i=1,\\dots,n-1 $\n\nThen:\n\n- $ b_1 = x $\n- $ b_2 = s_1 - x $\n- $ b_3 = s_2 - b_2 = s_2 - s_1 + x $\n- $ b_4 = s_3 - b_3 = s_3 - s_2 + s_1 - x $\n- $ b_5 = s_4 - b_4 = s_4 - s_3 + s_2 - s_1 + x $\n\nSo:\n\n$$\nb_i(x) = \n\\begin{cases}\nx + \\sum_{j=1}^{i-1} (-1)^{j+1} s_j & \\text{if } i \\text{ odd}, \\\\\n\\sum_{j=1}^{i-1} (-1)^j s_j - x & \\text{if } i \\text{ even}.\n\\end{cases}\n$$\n\nDefine $ c_i = \\sum_{j=1}^{i-1} (-1)^{j+1} s_j $ for odd $ i $,  \nand $ d_i = \\sum_{j=1}^{i-1} (-1)^j s_j $ for even $ i $\n\nThen:\n\n- $ b_i(x) = x + c_i $ for odd $ i $\n- $ b_i(x) = d_i - x $ for even $ i $\n\nThen non-negativity constraints:\n\n- For odd $ i $: $ x \\geq -c_i $\n- For even $ i $: $ x \\leq d_i $\n\nSo $ L = \\max_{i \\text{ odd}} (-c_i) $, $ U = \\min_{i \\text{ even}} d_i $\n\nLet $ T(x) = \\sum_{i=1}^n (a_i - b_i(x)) $\n\nLet $ R(x) = \\sum_{i=1}^n \\max(0, a_i - b_i(x)) $\n\nFind $ x^* = \\min \\{ x \\in \\mathbb{Z} \\cap [L, U] \\mid R(x) \\leq mk \\} $\n\nThen output $ T(x^*) $\n\nIf no such $ x $, output 0.\n\nBut since $ T(x) $ is linear and decreasing in $ x $, and $ R(x) $ is convex and piecewise linear, we can binary search on $ x \\in [L, U] $ to find the minimal $ x $ such that $ R(x) \\leq mk $, then compute $ T(x) $.\n\n---\n\n### Final Answer (as required):\n\n$$\n\\boxed{\n\\begin{aligned}\n&\\text{Let } s_i = a_i + a_{i+1} \\text{ for } i = 1, \\dots, n-1. \\\\\n&\\text{Define } c_i = \\sum_{j=1}^{i-1} (-1)^{j+1} s_j \\text{ for odd } i, \\quad d_i = \\sum_{j=1}^{i-1} (-1)^j s_j \\text{ for even } i. \\\\\n&\\text{Let } L = \\max_{\\substack{i=1,\\dots,n \\\\ i \\text{ odd}}} (-c_i), \\quad U = \\min_{\\substack{i=1,\\dots,n \\\\ i \\text{ even}}} d_i. \\\\\n&\\text{Define } b_i(x) = \n\\begin{cases}\nx + c_i & \\text{if } i \\text{ odd}, \\\\\nd_i - x & \\text{if } i \\text{ even}.\n\\end{cases} \\\\\n&\\text{Let } T(x) = \\sum_{i=1}^n (a_i - b_i(x)), \\quad R(x) = \\sum_{i=1}^n \\max(0, a_i - b_i(x)). \\\\\n&\\text{Find } x^* = \\min \\{ x \\in \\mathbb{Z} \\cap [L, U] \\mid R(x) \\leq mk \\}. \\\\\n&\\text{Output } T(x^*).\n\\end{aligned}\n}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF90C","tags":["greedy","math"],"sample_group":[["2 3 1\n2 3","0"],["3 2 2\n4 1 3","2"]],"created_at":"2026-03-03 11:00:39"}}