{"problem":{"name":"A. 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":"CF89A"},"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 array 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} $ for $ i = 1, 2, \\dots, n-1 $.\n\nJoe may perform up to $ m $ diamond-moving operations per minute for $ k $ minutes, for a total of at most $ m \\cdot k $ 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 $ j $.\n\nLet $ b = [b_1, b_2, \\dots, b_n] $ be the final configuration of diamonds in the cells after all operations.\n\n**Constraints:**\n- The adjacent sum vector must remain unchanged:  \n  $$\n  b_i + b_{i+1} = a_i + a_{i+1} \\quad \\text{for all } i = 1, 2, \\dots, n-1.\n  $$\n- The total number of diamond moves (i.e., net transfers between cells and pocket) is at most $ m \\cdot k $.\n\nLet $ T = \\sum_{i=1}^n a_i $ be the total diamonds initially.\n\nLet $ T' = \\sum_{i=1}^n b_i $ be the total diamonds remaining in the cells.\n\nThen, the amount Joe steals is $ L = T - T' $.\n\nWe wish to **maximize** $ L = T - T' $, subject to:\n1. $ b_i + b_{i+1} = a_i + a_{i+1} $ for all $ i = 1, \\dots, n-1 $,\n2. $ b_i \\in \\mathbb{Z}_{\\geq 0} $ for all $ i $,\n3. The total number of diamond movements required to transform $ a $ to $ b $ is at most $ m \\cdot k $.\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 **entire sequence $ b $** is determined by $ b_1 $, due to 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\\vdots\n$$\n\nIn general, for all $ i $, $ b_i $ is an **affine function of $ b_1 $**:\n\n$$\nb_i = (-1)^{i+1} b_1 + c_i\n$$\n\nfor some constants $ c_i $ determined by the original $ a $.\n\nThus, the set of all valid $ b $ is a **1-dimensional affine space** parameterized by $ b_1 $.\n\nWe require $ b_i \\geq 0 $ for all $ i $, so $ b_1 $ must lie in an interval $ [L_{\\min}, L_{\\max}] $, defined by the non-negativity constraints on all $ b_i $.\n\nLet $ b_1 = x $. Then $ b_i = (-1)^{i+1} x + c_i \\geq 0 $ for all $ i $.\n\nThis gives linear inequalities in $ x $, defining a closed interval $ [x_{\\min}, x_{\\max}] $.\n\nThen, the total diamonds remaining in the safe is:\n\n$$\nT' = \\sum_{i=1}^n b_i = \\sum_{i=1}^n \\left[ (-1)^{i+1} x + c_i \\right] = x \\cdot \\sum_{i=1}^n (-1)^{i+1} + \\sum_{i=1}^n c_i\n$$\n\nLet $ S = \\sum_{i=1}^n (-1)^{i+1} = \\begin{cases}\n1 & \\text{if } n \\text{ odd} \\\\\n0 & \\text{if } n \\text{ even}\n\\end{cases} $\n\nSo:\n- If $ n $ is even: $ T' = \\sum c_i $ (constant), so $ L = T - T' $ is fixed → Joe cannot steal anything beyond what's forced.\n- If $ n $ is odd: $ T' = x + C $, where $ C = \\sum c_i $, so $ L = T - x - C $, and to **maximize** $ L $, we must **minimize** $ x $.\n\nThus:\n\n> **Case 1: $ n $ even**  \n> The total diamonds in the safe is fixed under the adjacent-sum constraint. So Joe cannot steal any diamonds without triggering the alarm.  \n> $$\n> \\boxed{0}\n> $$\n\n> **Case 2: $ n $ odd**  \n> $ T' = x + C $, so $ L = T - x - C $.  \n> To maximize $ L $, minimize $ x $, subject to $ b_i = (-1)^{i+1} x + c_i \\geq 0 $ for all $ i $.  \n> Let $ x_{\\min} = \\max_i \\left( \\frac{ -c_i }{ (-1)^{i+1} } \\right) $ under the constraint $ b_i \\geq 0 $.  \n> Then maximum stealable diamonds:  \n> $$\n> L_{\\max} = T - x_{\\min} - C\n> $$\n\nBut we are also constrained by the **number of moves**.\n\nLet $ d_i = b_i - a_i $ be the net change in cell $ i $. The total number of diamond movements required is the **total variation** needed to go from $ a $ to $ b $, accounting for pocket transfers.\n\nEach diamond moved from cell to cell counts as 1 move, from cell to pocket as 1, from pocket to cell as 1.\n\nSo the total number of moves is the **total amount of diamonds removed from cells minus those added to cells**, but since pocket acts as buffer, the total moves = total diamonds **taken out** (to pocket) + total diamonds **put in** (from pocket).\n\nBut note: net change in cell $ i $ is $ d_i = b_i - a_i $.  \nLet $ D^+ = \\sum_{i: d_i > 0} d_i $ be total diamonds added to cells.  \nLet $ D^- = \\sum_{i: d_i < 0} (-d_i) $ be total diamonds removed from cells.\n\nThen total moves = $ D^+ + D^- $, since every diamond added required a move from pocket, every diamond removed required a move to pocket.\n\nBut note: $ D^+ = D^- + (T' - T) $? No.\n\nActually, total diamonds removed from cells = $ D^- $, total added = $ D^+ $, and net change: $ \\sum d_i = T' - T = -L $.\n\nBut $ D^+ - D^- = T' - T = -L $\n\nSo $ D^+ = D^- - L $\n\nThen total moves = $ D^+ + D^- = (D^- - L) + D^- = 2D^- - L $\n\nAlternatively, since total diamonds removed from cells = $ D^- $, and those go to pocket, and total added to cells = $ D^+ $, from pocket, then total moves = $ D^- + D^+ = D^- + (D^- - L) = 2D^- - L $\n\nBut we can also express total moves as:\n\n$$\n\\text{Total moves} = \\sum_{i=1}^n |d_i| = \\sum_{i=1}^n |b_i - a_i|\n$$\n\nThis is because each unit change in a cell requires one move (whether in or out), and moves between cells are equivalent to two moves (out of one, into another), but the problem counts **each diamond transfer** as one move regardless of direction.\n\nWait: the problem says:\n\n> One of the three following operations is regarded as moving a diamond:  \n> - moving a diamond from any cell to any other one,  \n> - moving a diamond from any cell to Joe's pocket,  \n> - moving a diamond from Joe's pocket to any cell.\n\nSo moving from cell $ i $ to cell $ j $ counts as **one** move.\n\nTherefore, the total number of moves is **not** $ \\sum |b_i - a_i| $, because if a diamond moves from cell $ i $ to cell $ j $, it reduces $ a_i $ by 1 and increases $ a_j $ by 1, so $ |d_i| + |d_j| = 2 $, but only **1 move** was made.\n\nSo we cannot use $ \\sum |d_i| $.\n\nWe need to compute the **minimum number of moves** to transform $ a $ to $ b $, where moves can be:\n- Cell → Cell (1 move, transfers 1 diamond),\n- Cell → Pocket (1 move),\n- Pocket → Cell (1 move).\n\nThis is equivalent to: we can transfer diamonds between any two cells at cost 1 per diamond, or to/from pocket at cost 1 per diamond.\n\nThis is a **transportation problem** with an extra \"sink/source\" (the pocket).\n\nThe minimum number of moves to go from $ a $ to $ b $ is:\n\n$$\n\\min \\left\\{ \\sum_{i \\ne j} x_{ij} + \\sum_i y_i + \\sum_i z_i \\right\\}\n$$\n\nsubject to:\n- $ b_i = a_i - \\sum_j x_{ji} + \\sum_j x_{ij} - y_i + z_i $\n- $ x_{ij} \\geq 0 $, $ y_i \\geq 0 $, $ z_i \\geq 0 $\n\nBut this is complex.\n\n**Better Insight:**\n\nWe are allowed to move diamonds arbitrarily between cells and pocket. The **minimum number of moves** to transform $ a $ to $ b $ is:\n\n$$\n\\text{Moves} = \\frac{1}{2} \\sum_{i=1}^n |d_i| + \\max(0, -\\sum d_i)\n$$\n\nWait — no.\n\nActually, the total net change is $ \\sum d_i = T' - T = -L $. So Joe stole $ L $ diamonds.\n\nThe total \"imbalance\" that must be corrected via internal transfers is $ \\sum_{d_i > 0} d_i = D^+ $, and $ \\sum_{d_i < 0} (-d_i) = D^- $, and $ D^+ - D^- = T' - T = -L $, so $ D^+ = D^- - L $.\n\nThe **minimum number of moves** is:\n\n- $ D^- $ diamonds removed from cells → to pocket: $ D^- $ moves.\n- $ D^+ $ diamonds added to cells ← from pocket: $ D^+ $ moves.\n- But we can also move diamonds **between cells** to reduce moves.\n\nEach diamond moved from a cell with surplus to one with deficit reduces both $ D^- $ and $ D^+ $ by 1, and costs only 1 move instead of 2.\n\nSo optimal strategy: move as many diamonds as possible **between cells**.\n\nThe maximum number of diamonds that can be moved between cells is $ \\min(D^-, D^+) $.\n\nThen:\n\n- Internal moves: $ \\min(D^-, D^+) $\n- Pocket moves: $ D^- - \\min(D^-, D^+) + D^+ - \\min(D^-, D^+) = |D^- - D^+| = L $\n\nSo total moves:\n\n$$\n\\text{Moves} = \\min(D^-, D^+) + L\n$$\n\nBut since $ D^+ = D^- - L $, then $ \\min(D^-, D^+) = D^+ = D^- - L $\n\nSo:\n\n$$\n\\text{Moves} = (D^- - L) + L = D^-\n$$\n\nWait — that can’t be right.\n\nLet’s take an example:\n\nInitial: [2, 0], target: [1, 1]. Then $ d = [-1, +1] $, $ D^- = 1, D^+ = 1, L = 0 $\n\nMove 1 diamond from cell 1 to cell 2: 1 move. Total moves = 1.\n\n$ D^- = 1 $, so moves = $ D^- = 1 $ — matches.\n\nAnother: Initial [3, 0], target [1, 1]. Then $ d = [-2, +1] $, $ D^- = 2, D^+ = 1, L = 1 $\n\nWe can move 1 diamond from cell 1 to cell 2 (1 move), and move 1 diamond from cell 1 to pocket (1 move). Total moves = 2.\n\n$ D^- = 2 $, so moves = $ D^- = 2 $ — matches.\n\nAnother: Initial [0, 0], target [1, 1]. $ d = [1,1] $, $ D^- = 0, D^+ = 2, L = -2 $? No, $ T' = 2, T = 0, L = -2 $? But Joe can't steal negative.\n\nWait: $ L = T - T' = 0 - 2 = -2 $, meaning Joe put in 2 diamonds — not stealing.\n\nBut we are maximizing stealing, so we consider $ L \\geq 0 $.\n\nIn our case, $ T' \\leq T $, so $ L \\geq 0 $.\n\nSo in general:\n\nLet $ D^- = \\sum_{d_i < 0} (-d_i) $ = total diamonds removed from cells.\n\nLet $ D^+ = \\sum_{d_i > 0} d_i $ = total diamonds added to cells.\n\nThen $ D^- - D^+ = T - T' = L $\n\nSo $ D^- = D^+ + L $\n\nTotal moves = $ D^- $ (because we can use internal transfers to cover $ D^+ $ diamonds, and the remaining $ L $ must go to pocket, so total moves = $ D^- $)\n\nWhy? Because:\n\n- We can transfer up to $ D^+ $ diamonds from cells with deficit to cells with surplus? No — we need to remove $ D^- $ diamonds from cells, and add $ D^+ $ to others.\n\nActually, the minimum number of moves is $ D^- $, because:\n\n- Every diamond that ends up **outside** the cells (in Joe’s pocket) must have been moved out at least once.\n- Every diamond that is moved from one cell to another reduces the need to move to/from pocket.\n- But since we are only allowed to move diamonds that are **in cells** to other places, the **total number of times a diamond leaves a cell** is exactly $ D^- $, and each such exit is one move.\n- Diamonds can be moved between cells, but each such move still requires one \"exit\" from a cell and one \"entry\" to another — but the entry doesn't count as a move if we're counting only operations (and each operation is one transfer).\n\nWait — the problem counts **each transfer** as one move, regardless of direction.\n\nSo if a diamond moves from cell A to cell B, that’s **one move**.\n\nIf a diamond moves from cell A to pocket, that’s **one move**.\n\nSo to go from $ a $ to $ b $, we need to account for:\n\n- The net outflow from each cell: $ a_i - b_i $ if positive = diamonds removed from cell $ i $.\n- The net inflow: $ b_i - a_i $ if positive = diamonds added to cell $ i $.\n\nThe total number of moves is the **minimum number of transfers** needed to achieve the net change.\n\nThis is a classic problem: the minimum number of moves to transform one distribution to another with transfers between any two positions and an external sink/source.\n\nThe answer is:\n\n> The minimum number of moves is equal to the **total outflow** from the cells, which is $ \\sum_{i=1}^n \\max(0, a_i - b_i) = D^- $\n\nBecause:\n- Every diamond that leaves a cell must be moved out in one operation.\n- Once it’s out, it can be moved to another cell (1 move) or to pocket (1 move).\n- But if it goes to another cell, it is then \"inflow\" to that cell, which doesn't require an additional move beyond the initial outflow.\n\nSo total moves = total diamonds removed from cells = $ \\sum_{i=1}^n \\max(0, a_i - b_i) = D^- $\n\nAnd since $ D^- = D^+ + L $, and $ D^+ \\geq 0 $, we have $ D^- \\geq L $\n\nSo constraint: $ D^- \\leq m \\cdot k $\n\nBut $ D^- = \\sum_{i=1}^n \\max(0, a_i - b_i) $\n\nAnd we want to **maximize** $ L = T - T' = T - \\sum b_i $\n\nSubject to:\n- $ b_i + b_{i+1} = a_i + a_{i+1} $ for all $ i $\n- $ b_i \\geq 0 $\n- $ \\sum_{i=1}^n \\max(0, a_i - b_i) \\leq m \\cdot k $\n\nAnd as established, if $ n $ is even, $ T' $ is fixed → $ L = 0 $\n\nIf $ n $ is odd, then $ b_i = (-1)^{i+1} x + c_i $, and $ T' = x + C $, so $ L = T - x - C $\n\nWe want to **minimize $ x $** to maximize $ L $, but subject to:\n1. $ b_i = (-1)^{i+1} x + c_i \\geq 0 $ → gives lower bound $ x \\geq x_{\\min} $\n2. $ \\sum_{i=1}^n \\max(0, a_i - b_i) \\leq m \\cdot k $\n\nLet $ f(x) = \\sum_{i=1}^n \\max(0, a_i - b_i(x)) $\n\nWe want the **smallest** $ x \\geq x_{\\min} $ such that $ f(x) \\leq m \\cdot k $, then $ L = T - x - C $\n\nBut $ f(x) $ is a **piecewise linear, non-increasing** function of $ x $, because as $ x $ increases, $ b_i(x) $ increases for odd $ i $, decreases for even $ i $, so $ a_i - b_i(x) $ decreases for odd $ i $, increases for even $ i $.\n\nWait: $ b_i(x) = (-1)^{i+1} x + c_i $\n\nSo for $ i $ odd: $ b_i = x + c_i $ → increases with $ x $\n\nFor $ i $ even: $ b_i = -x + c_i $ → decreases with $ x $\n\nSo $ a_i - b_i $:\n- For odd $ i $: $ a_i - x - c_i $ → decreases as $ x $ increases\n- For even $ i $: $ a_i + x - c_i $ → increases as $ x $ increases\n\nSo $ \\max(0, a_i - b_i) $:\n- For odd $ i $: decreases with $ x $\n- For even $ i $: increases with $ x $\n\nThus $ f(x) = \\sum \\max(0, a_i - b_i(x)) $ is **not monotonic** — it may have a minimum.\n\nBut we are trying to **minimize $ x $** to maximize $ L $, so we want the **smallest** $ x \\geq x_{\\min} $ such that $ f(x) \\leq m \\cdot k $\n\nWe can binary search on $ x $ over the feasible interval $ [x_{\\min}, x_{\\max}] $, compute $ f(x) $, and find the minimal $ x $ satisfying the constraint.\n\nThen $ L = T - x - C $\n\n**Final Answer:**\n\n- If $ n $ is even → $ \\boxed{0} $\n- If $ n $ is odd:\n  - Compute $ c_i $ from recurrence: $ b_1 = x $, $ b_2 = (a_1 + a_2) - x $, $ b_3 = (a_2 + a_3) - b_2 = a_3 - a_1 + x $, etc.\n  - Determine $ x_{\\min} = \\max_i \\left( \\frac{ -c_i }{ (-1)^{i+1} } \\right) $ such that $ b_i \\geq 0 $\n  - Let $ T' = x + C $, where $ C = \\sum c_i $\n  - Define $ f(x) = \\sum_{i=1}^n \\max(0, a_i - b_i(x)) $\n  - Find the minimal $ x \\in [x_{\\min}, x_{\\max}] $ such that $ f(x) \\leq m \\cdot k $\n  - Then answer = $ T - x - C $\n\nBut since $ m, k \\leq 10^9 $, and $ n \\leq 10^4 $, we can binary search on $ x $ over a bounded interval.\n\nThe values of $ c_i $ are linear combinations of $ a_j $, which are $ \\leq 10^5 $, so $ x $ is bounded by $ O(n \\cdot \\max a_i) \\leq 10^9 $, which is acceptable for binary search.\n\nThus, the algorithm is:\n\n1. If $ n $ even: return 0\n2. Else:\n   - Compute $ c_1 = 0 $, $ c_2 = a_1 + a_2 $, $ c_3 = a_3 - a_1 $, $ c_4 = a_4 + a_1 $, $ c_5 = a_5 - a_1 $, etc.  \n     General:  \n     $ c_1 = 0 $  \n     $ c_i = a_{i-1} + a_i - c_{i-1} $ for $ i \\geq 2 $  \n     Actually, from recurrence:  \n     $ b_i = (-1)^{i+1} x + c_i $  \n     $ b_1 = x = 1 \\cdot x + 0 \\Rightarrow c_1 = 0 $  \n     $ b_2 = (a_1 + a_2) - b_1 = (a_1 + a_2) - x = -x + (a_1 + a_2) \\Rightarrow c_2 = a_1 + a_2 $  \n     $ b_3 = (a_2 + a_3) - b_2 = (a_2 + a_3) - [(a_1 + a_2) - x] = x + (a_3 - a_1) \\Rightarrow c_3 = a_3 - a_1 $  \n     $ b_4 = (a_3 + a_4) - b_3 = (a_3 + a_4) - [x + a_3 - a_1] = -x + (a_4 + a_1) \\Rightarrow c_4 = a_4 + a_1 $  \n     So recurrence:  \n     $ c_1 = 0 $  \n     $ c_i = a_{i-1} + a_i - c_{i-1} $ for $ i \\geq 2 $  \n     But note: $ b_i + b_{i+1} = a_i + a_{i+1} $, so $ b_{i+1} = a_i + a_{i+1} - b_i $  \n     So $ c_{i+1} = a_i + a_{i+1} - c_i $, and the sign alternates.\n\n   - Compute $ C = \\sum_{i=1}^n c_i $\n   - Compute $ x_{\\min} = \\max_{i=1}^n \\left( \\frac{ -c_i }{ (-1)^{i+1} } \\right) $ under the constraint $ b_i \\geq 0 $  \n     i.e., for each $ i $:  \n     if $ i $ odd: $ x + c_i \\geq 0 \\Rightarrow x \\geq -c_i $  \n     if $ i $ even: $ -x + c_i \\geq 0 \\Rightarrow x \\leq c_i $  \n     So $ x \\geq \\max_{i \\text{ odd}} (-c_i) $, and $ x \\leq \\min_{i \\text{ even}} (c_i) $\n\n     So $ x_{\\min} = \\max_{i \\text{ odd}} (-c_i) $, $ x_{\\max} = \\min_{i \\text{ even}} (c_i) $\n\n   - If $ x_{\\min} > x_{\\max} $, no solution → but problem guarantees at least one check, so assume feasible.\n\n   - Define $ f(x) = \\sum_{i=1}^n \\max(0, a_i - b_i(x)) = \\sum_{i=1}^n \\max(0, a_i - [ (-1)^{i+1} x + c_i ]) $\n\n   - Binary search on $ x \\in [x_{\\min}, x_{\\max}] $ for the **smallest** $ x $ such that $ f(x) \\leq m \\cdot k $\n\n   - Answer: $ T - x - C $\n\nNote: Since $ f(x) $ is piecewise linear and convex? Not necessarily, but we can evaluate it in $ O(n) $ per evaluation, and binary search over $ O(\\text{range}) $, but range is up to $ 10^9 $, so $ \\log(10^9) \\approx 30 $ iterations, each $ O(n) $, total $ O(n \\log \\text{range}) \\approx 10^4 \\cdot 30 = 3 \\cdot 10^5 $, acceptable.\n\n**Final Output:**\n\n$$\n\\boxed{\n\\begin{cases}\n0 & \\text{if } n \\text{ is even} \\\\\nT - x^* - C & \\text{if } n \\text{ is odd}\n\\end{cases}\n}\n$$\n\nwhere $ x^* $ is the minimal $ x \\in [x_{\\min}, x_{\\max}] $ such that $ \\sum_{i=1}^n \\max(0, a_i - b_i(x)) \\leq m \\cdot k $, with $ b_i(x) = (-1)^{i+1} x + c_i $, $ c_i $ defined recursively by $ c_1 = 0 $, $ c_i = a_{i-1} + a_i - c_{i-1} $ for $ i \\geq 2 $, $ C = \\sum c_i $, $ T = \\sum a_i $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF89A","tags":["greedy"],"sample_group":[["2 3 1\n2 3","0"],["3 2 2\n4 1 3","2"]],"created_at":"2026-03-03 11:00:39"}}