C. Array Splitting

You are given a sorted array a1,a2,…,ana1,a2,…,an (for each index i>1i>1 condition ai≥ai−1ai≥ai−1 holds) and an integer kk.

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

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

Calculate the minimum cost you can obtain by dividing the array aa into kk non-empty consecutive subarrays.

Input

The first line contains two integers nn and kk (1≤k≤n≤3⋅1051≤k≤n≤3⋅105).

The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109, ai≥ai−1ai≥ai−1).

Output

Print the minimum cost you can obtain by dividing the array aa into kk nonempty consecutive subarrays.

Examples

input

6 3
4 8 15 16 23 42

output

12

input

4 4
1 3 3 7

output

0

input

8 1
1 1 2 3 5 8 13 21

output

20

题意：

给出一个长度为n的有序数组，将其分成m个小数组，使得每个数组最后一个元素减去第一个元素的值为的总和最小

思路：

每个小数组前后元素的差值等于各相邻元素差值的总和，所以将每个相邻元素的差值存储到一个数组里，找出最大的几个差值，也就是切断位置，使得最后的数组元素总差值最小，那么求总差值就是把前几个小的差值加起来即可

切断成m个数组，需要切m-1次，差值数组***有n-1个元素，也就是要求前(n-1)-(m-1)==n-m个元素的值

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))

int a[300005],b[300005];

int main()
{
	ll n,m,i,s=0;
	cin>>n>>m;
	for(i=0;i<n;i++)
	{
		cin>>a[i];
		if(i>0)
			b[i-1]=a[i]-a[i-1];
	}
	sort(b,b+n-1);
	int t=n-m;        //切成m段，切m-1次，n-1个b，计算前n-1-(m-1)=n-m 个最小的元素
	for(i=0;i<t;i++)
		s+=b[i];
	cout<<s<<endl;
	return 0; 
}