求调喵！

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=300005,INF=2e6;

int n,k;
int val[N];

int ans,dp[N][2],g[N][2];
bool check(int delta) {
	memset(dp,0,sizeof(dp));
	memset(g,0,sizeof(g));
	
	for(int i=1;i<=n+1;++i) {
		dp[i][1]=dp[i-1][0]+val[i]+delta,g[i][1]=g[i-1][0]+1;
		if(make_pair(-dp[i-1][0],g[i-1][0]) < make_pair(-dp[i-1][1],g[i-1][1]))
			dp[i][0]=dp[i-1][0],g[i][0]=g[i-1][0];
		else
			dp[i][0]=dp[i-1][1],g[i][0]=g[i-1][1];
	}
	if(g[n+1][0]<=k) ans=max(ans,dp[n+1][0]-g[n+1][0]*delta);
	return g[n+1][0];
}

signed main() {
	cin >> n >> k;
	for(int i=1;i<=n;++i) cin >> val[i];
	
	int l=-INF,r=0,mid;
	while(l<=r) {
		mid=l+r>>1;
		if(check(mid)>k) r=mid-1;
		else l=mid+1;
	}
	
	cout << ans;
	
	return 0;
}