AT_tenka1_2016_qualB_e 天下一合体

高桥君有一个长度为 $N$ 的数列 $a_1,\ a_2,\ ...,\ a_N$。他可以多次进行以下操作： - 从数列中选择相邻的 $2$ 个元素，将这两个元素相加并合并为一个元素。也就是说，用它们的和替换这两个元素。 只要数列中的元素个数不少于 $M$，他就可以任意多次进行上述操作。 高桥君希望使数列中所有元素的绝对值之和最小。你的任务是替高桥君求出这个最小值。

输入以如下格式从标准输入读入： > $N$ $M$ $a_1$ $a_2$ ... $a_N$

输出一行表示所求的最小值。输出末尾需换行。

## 限制条件 - $1 \leq N \leq 20,\!000$ - $1 \leq M \leq \min(100, N)$ - $|a_i| \leq 10^9$ ## 样例解释 1 - 首先选择 $[2, -4, 3, -1]$ 的第 1 个和第 2 个元素，得到 $[-2, 3, -1]$。 - 然后选择 $[-2, 3, -1]$ 的第 1 个和第 2 个元素，得到 $[1, -1]$。 - 此时答案为 $|1| + |-1| = 2$，这是最优的。 ## 样例解释 2 - 对第 2 个和第 3 个元素进行 5 次操作，得到 $[0, -1, 5, -4]$。 - 然后选择第 3 个和第 4 个元素，得到 $[0, -1, 1]$。 - 此时答案为 $|0| + |-1| + |1| = 2$，这是最优的。 由 ChatGPT 4.1 翻译