#include <bits/stdc++.h>
#define F first
#define S second
#define ll long long
#define pii pair<ll,ll>
const int mxN = 3e5 + 5;
const int mod = 1e9 + 7;
using namespace std;
bool operator>(pair<ll,int> a,pair<ll,int>b){
return make_pair(a.F,-1 * a.S) > make_pair(b.F, -1 * b.S);
}
bool operator<(pair<ll,int> a,pair<ll,int>b){
return make_pair(a.F,-1 * a.S) < make_pair(b.F, -1 * b.S);
}
int n,k;
int a[mxN];
pair<ll,int> dp[2][2];
pair<ll,int> num;
ll ans;
ll l = 0,r = 1e12,md;
bool solve(ll lam){
// cout<<lam<<'\n';
for(int i = 0;i <= 1;i++){
dp[i][0] = make_pair(0,0);
dp[i][1] = make_pair(0,0);
}
for(int i = 1;i <= n;i++){
// cout<<x<<' '<<(y)<<'\n';
int x = (i & 1),y = (~i & 1);
dp[x][0] = max(dp[(y)][0],dp[(y)][1]);
dp[x][1] = make_pair(dp[(y)][0].F + a[i] - lam,dp[y][0].S + 1);
if(i > 1) dp[x][1] = max(dp[x][1],make_pair(dp[y][1].F + a[i],dp[y][1].S));
// cout<<dp[x][0].F<<' '<<dp[x][0].S<<' '<<dp[x][1].F<<' '<<dp[x][1].S<<'\n';
}
num = max(dp[n & 1][0],dp[n & 1][1]);
// cout<<num.F<<' '<<num.S<<'\n';
return (num.S <= k);
}
signed main(){
cin >>n>>k;
for(int i = 1;i <= n;i++) cin >>a[i];
while(l < r){
md = (l + r) / 2;
if(solve(md)){
r = md;
ans = num.F + num.S * md;
}else l = md + 1;
}
cout<<ans;
}
