正解推荐（贪心做法）：

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define N 200007
using namespace std;
struct Place
{
    int val,l,r;
    
}p[N];
struct Node
{
    int val,id;
    bool operator <(Node it) const
    {
        return val<it.val;
    } 
};
int n,m,ans;
bool vis[N];
priority_queue<Node> q;
void Del(int x)
{
    p[x].l=p[p[x].l].l;
    p[x].r=p[p[x].r].r;
    p[p[x].l].r=x;
    p[p[x].r].l=x;
}
int main()
{
    scanf("%d%d",&n,&m);
    if(n<m*2)
    {
        printf("Error!");
        return 0;
    }
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&p[i].val);
        p[i].l=i-1;
        p[i].r=i+1;
        q.push((Node){p[i].val,i});
    }
    p[1].l=n,p[n].r=1;
    for(int i=1;i<=m;++i)
    {
        while(vis[q.top().id])
            q.pop();
        Node now=q.top();
        q.pop();
        ans+=now.val;
        vis[p[now.id].l]=vis[p[now.id].r]=1;
        p[now.id].val=p[p[now.id].l].val+p[p[now.id].r].val-p[now.id].val;
        q.push((Node){p[now.id].val,now.id});
        Del(now.id);
    }
        
    printf("%d",ans);
    return 0;
}

DP+二分：

/*
这里给出一种(虽然很简单但是没人写题解的)wqs二分的方法。

首先由于 m 的限制，加上权值会有负数所以多选和少选都有可能导致结果不优，
所以很容易想到要去wqs二分。二分之后就变成了求解没有 m 的限制的最大值问题。自然的想法是考虑 
f i表示前 i 个坑种树的最大收益，那么转移就是考虑第 i 个坑种不种，
即 f i =max{f i−1 ,f i−2 +val i }。

但是这个地方存在一个问题，就是第 n 个和第 1 个之间可能存在不合法。
于是就理所应当地再记一维 0/1 表示第 1 个坑到底种不种树，转移到 n 的时候特判一下。 
这样就可以解决了。
*/
/*
这里给出一种(虽然很简单但是没人写题解的)wqs二分的方法。

首先由于 m 的限制，加上权值会有负数所以多选和少选都有可能导致结果不优，
所以很容易想到要去wqs二分。二分之后就变成了求解没有 m 的限制的最大值问题。自然的想法是考虑 
f i表示前 i 个坑种树的最大收益，那么转移就是考虑第 i 个坑种不种，
即 f i =max{f i−1 ,f i−2 +val i }。

但是这个地方存在一个问题，就是第 n 个和第 1 个之间可能存在不合法。
于是就理所应当地再记一维 0/1 表示第 1 个坑到底种不种树，转移到 n 的时候特判一下。 
这样就可以解决了。
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
const int N = 200010 ;
ll res ;
int m, n ;
int df[N] ;
ll f[N][2] ;
int base[N] ;
int cnt[N][2] ;

bool check(int x){
	f[1][0] = 0 ; cnt[1][0] = 0 ;
	f[1][1] = base[1] + x, cnt[1][1] = 1 ;
	for (int i = 2 ; i < n ; ++ i){
		if (f[i - 1][0] > f[i - 2][0] + x + base[i])
			f[i][0] = f[i - 1][0], cnt[i][0] = cnt[i - 1][0] ;
		else if (f[i - 1][0] < f[i - 2][0] + x + base[i]) 
			f[i][0] = f[i - 2][0] + x + base[i], cnt[i][0] = cnt[i - 2][0] + 1 ;
		else 
			f[i][0] = f[i - 1][0], cnt[i][0] = max(cnt[i - 1][0], cnt[i - 2][0] + 1) ;

		if (f[i - 1][1] > f[i - 2][1] + x + base[i])
			f[i][1] = f[i - 1][1], cnt[i][1] = cnt[i - 1][1] ;
		else if (f[i - 1][1] < f[i - 2][1] + x + base[i]) 
			f[i][1] = f[i - 2][1] + x + base[i], cnt[i][1] = cnt[i - 2][1] + 1 ;
		else 
			f[i][1] = f[i - 1][1], cnt[i][1] = max(cnt[i - 1][1], cnt[i - 2][1] + 1) ;
	}
	f[n][1] = f[n - 1][1] ; 
	cnt[n][1] = cnt[n - 1][1] ;
	if (f[n - 1][0] > f[n - 2][0] + x + base[n])
		f[n][0] = f[n - 1][0], cnt[n][0] = cnt[n - 1][0] ;
	else if (f[n - 1][0] < f[n - 2][0] + x + base[n]) 
		f[n][0] = f[n - 2][0] + x + base[n], cnt[n][0] = cnt[n - 2][0] + 1 ;
	else 			
		f[n][0] = f[n - 1][0], cnt[n][0] = max(cnt[n - 1][0], cnt[n - 2][0] + 1) ;
	if (f[n][0] > f[n][1]){
		res = f[n][0] - (ll)x * m ; 
		return (bool)(cnt[n][0] >= m) ;
	}
	else{
		res = f[n][1] - (ll)x * m ; 
		return (bool)(cnt[n][1] >= m) ;
	}
}
int main(){
	cin >> n >> m ; 
	for (int i = 1 ; i <= n ; ++ i) 
		scanf("%d", &base[i]) ; 
	if (m > n / 2) return puts("Error!"), 0 ;
	int l = -2e9, r = 2e9, mid, ans ; 
	while (l <= r){
		mid = (l + r) >> 1 ; 
//		cout << l << " " << r << endl ; 
		if (check(mid)) ans = mid, r = mid - 1 ;
		else l = mid + 1 ;
	}	
	check(ans) ; cout << res << endl ; return 0 ;
}