#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
ll n,k;
ld arr[300005];
pair<ld,ll> dp[300005][2];
ld dpval,lab;
bool check(ld lambda){
dp[0][0]={0,0};
dp[0][1]={-1e18,0};
for(int i=1;i<=n;i++){
dp[i][1]={dp[i-1][1].first+arr[i],dp[i-1][1].second};
if(dp[i-1][0].first+arr[i]-lambda>=dp[i][1].first){
dp[i][1]={dp[i-1][0].first+arr[i]-lambda,dp[i-1][0].second+1};
}
if(dp[i-1][1].first>dp[i-1][0].first){
dp[i][0]={dp[i-1][1].first,dp[i-1][1].second};
}
else if(dp[i-1][1].first==dp[i-1][0].first){
if(dp[i-1][1].second>dp[i-1][0].second){
dp[i][0]=dp[i-1][0];
}
else{
dp[i][0]=dp[i-1][1];
}
}
else{
dp[i][0]=dp[i-1][0];
}
}
if(dp[n][0].first>dp[n][1].first){
dpval=dp[n][0].first;
lab=dp[n][0].second;
return dp[n][0].second<=k;
}
else if(dp[n][0].first==dp[n][1].first){
dpval=dp[n][0].first;
lab=min(dp[n][0].second,dp[n][1].second);
return min(dp[n][0].second,dp[n][1].second)<=k;
}
else{
dpval=dp[n][1].first;
lab=dp[n][1].second;
return dp[n][1].second<=k;
}
}
ld Aliens(){
ld l=0,r=1e9*300000;
while(r-l>=1e-6){
ld mid=(l+r)/2;
if(check(mid)){
r=mid;
}
else{
l=mid;
}
}
// cout<<dpval<<" "<<lab<<" "<<l<<"\n";
return dpval+lab*l;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>arr[i];
}
ld ans=Aliens();
cout<<(long long)round(ans)<<"\n";
}
