#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define int long long
using namespace std;
template<class T>inline void read(T &x)
{
    x=0;register char c=getchar();register bool f=0;
    while(!isdigit(c))f^=c=='-',c=getchar();
    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    if(f)x=-x;
}
template<class T>inline void print(T x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar('0'+x%10);
}
int n,k;
int cnt[5000005];
int f[5000005];
int bas[5000005];
int ans;
bool check(int x){
	if(bas[1]+x>=0){
	f[1]=bas[1]+x;
	cnt[1]=1;
	}else{
	f[1]=0;
		cnt[1]=0;
	}
	for(int i=2;i<=n;++i){
		if(f[i-1]>f[i-2]+bas[i]+x){
			f[i]=f[i-1];
			cnt[i]=cnt[i-1];
		}else if(f[i-1]<f[i-2]+bas[i]+x){
			f[i]=f[i-2]+bas[i]+x;
			cnt[i]=cnt[i-2]+1;
		}else{
			f[i]=f[i-1];
			cnt[i]=min(cnt[i-1],cnt[i-2]+1);
		}
	}
	return cnt[n]<=k;
}
signed main(){
	read(n);read(k);
	for(int i=1;i<=n;++i){
		read(bas[i]);
	}
	int l=-10000006;
	int r=10000006;
	while(l<=r){
//		cout<<l<<endl;
		int mid=(l+r)/2;
		if(check(mid)){
			l=mid+1;
			ans=f[n]-mid*k;
		}else{
			r=mid-1;
		}
	}
	cout<<ans;
	return 0;
}