{"raw_statement":[{"iden":"statement","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."},{"iden":"input","content":"The 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_."},{"iden":"output","content":"Output a single integer — the smallest possible sum of values of these subarrays of some partition of _a_."},{"iden":"examples","content":"Input\n\n3 5\n1 2 3\n\nOutput\n\n6\n\nInput\n\n12 10\n1 1 10 10 10 10 10 10 9 10 10 10\n\nOutput\n\n92\n\nInput\n\n7 2\n2 3 6 4 5 7 1\n\nOutput\n\n17\n\nInput\n\n8 4\n1 3 4 5 5 3 4 1\n\nOutput\n\n23"},{"iden":"note","content":"In 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."}],"translated_statement":[{"iden":"statement","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"},{"iden":"input","content":"第一行包含两个整数 #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] 的元素。"},{"iden":"output","content":"请输出一个整数——某个对 #cf_span[a] 的划分中，这些子数组的值之和的最小可能值。"},{"iden":"examples","content":"输入\n3 5\n1 2 3\n输出\n6\n\n输入\n12 10\n1 1 10 10 10 10 10 10 9 10 10 10\n输出\n92\n\n输入\n7 2\n2 3 6 4 5 7 1\n输出\n17\n\n输入\n8 4\n1 3 4 5 5 3 4 1\n输出\n23"},{"iden":"note","content":"在第一个示例中，任何划分的和均为 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。"}],"sample_group":[],"show_order":[],"formal_statement":"**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.","simple_statement":null,"has_page_source":false}