#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define mp make_pair
#define pr pair<ll,ll>
#define fi first
#define se second
const int N=3e5+4;
pr f[N][2];
ll a[N],n,k;
pr chk(ll x){
f[0][0]={0,0};
f[0][1]={-(ll)4e15,-(ll)4e15};
for(int i=1;i<=n;++i){
f[i][1]=max(mp(f[i-1][1].fi+a[i],f[i-1][1].se),mp(f[i-1][0].fi+a[i]-x,f[i-1][0].se+1));
f[i][0]=max((pair<ll,ll>)f[i-1][0],(pair<ll,ll>)f[i-1][1]);
}
return(max({f[n][0],f[n][1]}));
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>k;
for(int i=1;i<=n;++i)
cin>>a[i];
ll l=0,r=3e14,ans=0;
while(l<=r){
ll λ=(l+r)/2;
auto R=chk(λ);
if(R.se>k)l=λ+1;
else{
ans=R.fi+λ*R.se;
r=λ-1;
}
}
cout<<ans;
}
