#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
mt19937 rng(42);
pair<ll,ll> anslambda(ll lambda,const vector<ll>& v,vector<vector<ll>>& dp,vector<vector<int>>& segs){
int n=v.size();
dp[0][0]=0;
dp[0][1]=v[0]-lambda;
segs[0][0]=0;
segs[0][1]=1;
for(int i=1;i<n;i++){
//dp[i][0]=max(ld(0),ld(dp[i-1][0]));
//dp[i][0]=max(ld(dp[i][0]),ld(dp[i-1][1]));
dp[i][0]=0;
segs[i][0]=0;
if(dp[i][0]<dp[i-1][0]){
dp[i][0]=dp[i-1][0];
segs[i][0]=segs[i-1][0];
}
if(dp[i][0]<dp[i-1][1]){
dp[i][0]=dp[i-1][1];
segs[i][0]=segs[i-1][1];
}
//dp[i][1]=max(ld(v[i]),dp[i-1][0]+v[i]-lambda);
//dp[i][1]=max(ld(dp[i][1]),ld(dp[i-1][1]+v[i]));
dp[i][1]=v[i]-lambda;
segs[i][1]=1;
if(dp[i][1]<dp[i-1][0]+v[i]-lambda){
dp[i][1]=dp[i-1][0]+v[i]-lambda;
segs[i][1]=segs[i-1][0]+1;
}
if(dp[i][1]<dp[i-1][1]+v[i]){
dp[i][1]=dp[i-1][1]+v[i];
segs[i][1]=segs[i-1][1];
}
}
if(dp[n-1][0]>dp[n-1][1]){
return {dp[n-1][0]+segs[n-1][0]*lambda,segs[n-1][0]};
}else{
return {dp[n-1][1]+segs[n-1][1]*lambda,segs[n-1][1]};
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n,k;
cin>>n>>k;
vector<vector<ll>>dp(n,vector<ll>(2,0));
vector<vector<int>>segs(n,vector<int>(2,0));
vector<ll>v(n,0);
for(int i=0;i<n;i++){
cin>>v[i];
//v[i]=rng()%((int)1e+9);
}
/*for(ld lambda=0;lambda<10;lambda+=0.1){
pair<ld,ld>p=anslambda(lambda,v);
cout<<p.first<<" "<<p.second<<"\n";
}*/
//busco el menor lambda con p.second<=k
ll l=0;
ll r=1e18;
while(l<r){
ll mid=l+(r-1)/2;
pair<ll,ll>p=anslambda(mid,v,dp,segs);
if(p.second<=k)
r=mid;
else
l=mid+1;
//cout<<mid<<p.first<<" "<<p.second<<"\n";
}
pair<ll,ll>p=anslambda(r,v,dp,segs);
cout<<ll(round(p.first))<<"\n";
return 0;
}
