# codeforces 1197 C Array Splitting 贪心

2019/7/24 17:24:14 人评论 次浏览 分类：学习教程

http://codeforces.com/problemset/problem/1197/C

You are given a sorted array a1,a2,…,an (for each index i>1 condition ai≥ai−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 ∑i=1k(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.

Input

The first line contains two integers n

and k (1≤k≤n≤3⋅105

).

The second line contains n

integers a1,a2,…,an (1≤ai≤109, ai≥ai−1

).

Output

Print the minimum cost you can obtain by dividing the array a

into k

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
```

Note

In the first test we can divide array a

in the following way: [4,8,15,16],,.

``````#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;

int n,k;
int a;
int d;
ll ans=0;

int main()
{
scanf("%d %d",&n,&k);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
for(int i=0;i<n-1;i++)
d[i]=a[i+1]-a[i];
sort(d,d+n-1);
ans=a[n-1]-a;
int i=n-2;
while(--k)
ans-=d[i--];
printf("%lld\n",ans);
return 0;
}
``````

暂无相关的资讯...

-->