{"problem":{"name":"E. Cashback","description":{"content":"_Since you are the best Wraith King, Nizhniy Magazin «Mir» at the centre of Vinnytsia is offering you a discount._ You are given an array _a_ of length _n_ and an integer _c_. The value of some arra","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF940E"},"statements":[{"statement_type":"Markdown","content":"_Since you are the best Wraith King, Nizhniy Magazin «Mir» at the centre of Vinnytsia is offering you a discount._\n\nYou are given an array _a_ of length _n_ and an integer _c_.\n\nThe value of some array _b_ of length _k_ is the sum of its elements except for the smallest. For example, the value of the array \\[3, 1, 6, 5, 2\\] with _c_ = 2 is 3 + 6 + 5 = 14.\n\nAmong all possible partitions of _a_ into contiguous subarrays output the smallest possible sum of the values of these subarrays.\n\n## Input\n\nThe first line contains integers _n_ and _c_ (1 ≤ _n_, _c_ ≤ 100 000).\n\nThe second line contains _n_ integers _a__i_ (1 ≤ _a__i_ ≤ 109) — elements of _a_.\n\n## Output\n\nOutput a single integer — the smallest possible sum of values of these subarrays of some partition of _a_.\n\n[samples]\n\n## Note\n\nIn the first example any partition yields 6 as the sum.\n\nIn the second example one of the optimal partitions is \\[1, 1\\], \\[10, 10, 10, 10, 10, 10, 9, 10, 10, 10\\] with the values 2 and 90 respectively.\n\nIn the third example one of the optimal partitions is \\[2, 3\\], \\[6, 4, 5, 7\\], \\[1\\] with the values 3, 13 and 1 respectively.\n\nIn the fourth example one of the optimal partitions is \\[1\\], \\[3, 4, 5, 5, 3, 4\\], \\[1\\] with the values 1, 21 and 1 respectively.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"_由于你是最强大的幽灵之王，位于文尼察市中心的 Nizhniy Magazin «Mir» 正为你提供折扣。_ \n\n给定一个长度为 #cf_span[n] 的数组 #cf_span[a] 和一个整数 #cf_span[c]。 \n\n某个长度为 #cf_span[k] 的数组 #cf_span[b] 的值定义为：其所有元素之和减去最小的元素。例如，数组 #cf_span[[3, 1, 6, 5, 2]] 在 #cf_span[c = 2] 时的值为 #cf_span[3 + 6 + 5 = 14]。 \n\n在所有可能的将 #cf_span[a] 划分为连续子数组的方案中，请输出这些子数组的值之和的最小可能值。 \n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[c]（#cf_span[1 ≤ n, c ≤ 100 000]）。 \n\n第二行包含 #cf_span[n] 个整数 #cf_span[ai]（#cf_span[1 ≤ ai ≤ 10^9]）——数组 #cf_span[a] 的元素。 \n\n请输出一个整数——某个对 #cf_span[a] 的划分中，这些子数组的值之和的最小可能值。 \n\n在第一个示例中，任何划分的和均为 6。 \n\n在第二个示例中，一种最优划分是 #cf_span[[1, 1], [10, 10, 10, 10, 10, 10, 9, 10, 10, 10]]，其值分别为 2 和 90。 \n\n在第三个示例中，一种最优划分是 #cf_span[[2, 3], [6, 4, 5, 7], [1]]，其值分别为 3、13 和 1。 \n\n在第四个示例中，一种最优划分是 #cf_span[[1], [3, 4, 5, 5, 3, 4], [1]]，其值分别为 1、21 和 1。 \n\n## Input\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[c]（#cf_span[1 ≤ n, c ≤ 100 000]）。第二行包含 #cf_span[n] 个整数 #cf_span[ai]（#cf_span[1 ≤ ai ≤ 10^9]）——数组 #cf_span[a] 的元素。\n\n## Output\n\n请输出一个整数——某个对 #cf_span[a] 的划分中，这些子数组的值之和的最小可能值。\n\n[samples]\n\n## Note\n\n在第一个示例中，任何划分的和均为 6。在第二个示例中，一种最优划分是 #cf_span[[1, 1], [10, 10, 10, 10, 10, 10, 9, 10, 10, 10]]，其值分别为 2 和 90。在第三个示例中，一种最优划分是 #cf_span[[2, 3], [6, 4, 5, 7], [1]]，其值分别为 3、13 和 1。在第四个示例中，一种最优划分是 #cf_span[[1], [3, 4, 5, 5, 3, 4], [1]]，其值分别为 1、21 和 1。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, c \\in \\mathbb{Z}^+ $ with $ 1 \\leq n, c \\leq 100{,}000 $.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers with $ 1 \\leq a_i \\leq 10^9 $.  \n\nFor any non-empty subarray $ B = (b_1, b_2, \\dots, b_k) $, define its *value* as:  \n$$\n\\text{value}(B) = \\sum_{i=1}^k b_i - \\min(B)\n$$  \nif $ k \\geq c $, and $ \\text{value}(B) = \\sum_{i=1}^k b_i $ if $ k < c $.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 100{,}000 $  \n2. $ 1 \\leq c \\leq 100{,}000 $  \n3. $ 1 \\leq a_i \\leq 10^9 $ for all $ i \\in \\{1, \\dots, n\\} $\n\n**Objective**  \nPartition $ A $ into $ m $ contiguous non-empty subarrays $ B_1, B_2, \\dots, B_m $ such that the total sum  \n$$\n\\sum_{j=1}^m \\text{value}(B_j)\n$$  \nis minimized. Output this minimum total sum.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF940E","tags":["data structures","dp","greedy","math"],"sample_group":[["3 5\n1 2 3","6"],["12 10\n1 1 10 10 10 10 10 10 9 10 10 10","92"],["7 2\n2 3 6 4 5 7 1","17"],["8 4\n1 3 4 5 5 3 4 1","23"]],"created_at":"2026-03-03 11:00:39"}}