A12862. Array Splitting

You are given a sorted array $a_1, a_2, \dots, a_n$ (for each index $i > 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.

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}$ ).

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

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