CF1197C.Array Splitting

You are given a sorted array $a_1, a_2, \dots, a_n$ (for each index $i \gt 1$ condition $a_i \ge a_{i-1}$ holds) and an integer $k$.

You are asked to divide this array into $k$ non-empty consecutive subarrays. Every element in the array should be included in exactly one subarray.

Let $max(i)$ be equal to the maximum in the $i$-th subarray, and $min(i)$ be equal to the minimum in the $i$-th subarray. The cost of division is equal to $\sum\limits_{i=1}^{k} (max(i) - min(i))$. For example, if $a = [2, 4, 5, 5, 8, 11, 19]$ and we divide it into $3$ subarrays in the following way: $[2, 4], [5, 5], [8, 11, 19]$, then the cost of division is equal to $(4 - 2) + (5 - 5) + (19 - 8) = 13$.

Calculate the minimum cost you can obtain by dividing the array $a$ into $k$ non-empty consecutive subarrays.

给你一个已排序的数组 $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$ 个非空连续子数组所能得到的最小代价。

The first line contains two integers $n$ and $k$ ($1 \le k \le n \le 3 \cdot 10^5$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($ 1 \le a_i \le 10^9$, $a_i \ge a_{i-1}$).

第一行包含两个整数 $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}$）。

Print the minimum cost you can obtain by dividing the array $a$ into $k$ nonempty consecutive subarrays.

输出将数组 $a$ 划分为 $k$ 个非空连续子数组所能得到的最小代价。

In the first test we can divide array $a$ in the following way: $[4, 8, 15, 16], [23], [42]$.

在第一个测试中，我们可以将数组 $a$ 按如下方式划分：$[4, 8, 15, 16], [23], [42]$。