//https://oj.uz/problem/view/NOI19_feast
#include<bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
#define ll long long
#define endl '\n'
int n,k,rec[300005][2];
ll a[300005];
long double dp[300005][2];
bool check(long double x){
for(int i=0;i<=n;i++)
for(int j=0;j<2;j++)
dp[i][j]=-1000000000000000000;
dp[0][0]=0;
for(int i=1;i<=n;i++){
if(dp[i-1][0]-x==dp[i-1][1])
dp[i][1]=dp[i-1][1],rec[i][1]=max(rec[i-1][0]+1,rec[i-1][1]);
else if(dp[i-1][0]-x>dp[i-1][1])
dp[i][1]=dp[i-1][0]-x,rec[i][1]=rec[i-1][0]+1;
else dp[i][1]=dp[i-1][1],rec[i][1]=rec[i-1][1];
dp[i][1]+=a[i];
if(dp[i-1][0]==dp[i-1][1])
dp[i][0]=dp[i-1][0],rec[i][0]=max(rec[i-1][0],rec[i-1][1]);
else if(dp[i-1][0]>dp[i-1][1])
dp[i][0]=dp[i-1][0],rec[i][0]=rec[i-1][0];
else dp[i][0]=dp[i-1][1],rec[i][0]=rec[i-1][1];
}
if(dp[n][0]>dp[n][1]) return rec[n][0]>=k;
else if(dp[n][0]<dp[n][1]) return rec[n][1]>=k;
else return max(rec[n][0],rec[n][1])>=k;
}
int 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=1000000000000000000,mid;
while(l<=r){
mid=(l+r)/2;
if(check(1.0*mid/1000000000)) l=mid+1;
else r=mid-1;
}
check(1.0*r/1000000000);
cout<<(long long)round(1.0*r/1000000000*k+max(dp[n][0],dp[n][1]))<<endl;
return 0;
}
