给定一个排序数组 $$$a_1, a_2, \dots, a_n$$$ (对于每个索引 $$$i > 1$$$ 条件 $$$a_i \ge a_{i-1}$$$ 成立)和一个整数 $$$k$$$。
要求您将此数组划分为 $$$k$$$ 个非空连续子数组。数组中的每个元素都应该包含在一个子数组中。
令 $$$max(i)$$$ 等于第 $$$i$$$ 个子数组中的最大值,$$$min(i)$$$ 等于第 $$$i$$$ 个子数组中的最小值。除法成本等于 $$$\sum\limits_{i=1}^{k} (max(i) - min(i))$$$。例如,如果 $$$a = [2, 4, 5, 5, 8, 11, 19]$$$ 并且我们按以下方式将其划分为 $$$3$$$ 子数组:$$$[2, 4], [5, 5], [8, 11, 19]$$$,则划分成本等于 $$$(4 - 2) + (5 - 5) + (19 - 8) = 13$$$。
计算将数组 $$$a$$$ 划分为 $$$k$$$ 非空连续子数组可以获得的最小成本。
输入
第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 3 \cdot 10^5$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$ 1 \le a_i \le 10^9$$$, $$$a_i \ge a_{i-1}$$$)。
输出
打印通过将数组 $$$a$$$ 分成 $$$k$$$ 非空连续子数组可以获得的最小成本。
示例
输入 #1
6 3 4 8 15 16 23 42
输出 #1
12
输入 #2
4 4 1 3 3 7
输出 #2
0
输入 #3
8 1 1 1 2 3 5 8 13 21
输出 #3
20
注意
在第一个测试中,我们可以按以下方式划分数组 $$$a$$$:$$$[4, 8, 15, 16], [23], [42]$$$。