#include <bits/stdc++.h>
using namespace std;
#define fst first
#define snd second
#define fore(i,a,b) for(auto i=a; i<b; i++)
#define forn(i,n) fore(i,0,n)
typedef long long ll;
const int MAXN = 3e5+10;
const ll INF = 1e9+10;
int n, k;
ll a[MAXN], lambda;
ll dp[MAXN][2], cnt[MAXN][2];
ll solve(int i, int flag){
if(i==n) return cnt[i][flag]=0;
ll& ret = dp[i][flag];
if(ret != -1) return ret;
cnt[i][flag]=0;
if(flag==0){
ret = solve(i+1,0);
cnt[i][flag]=cnt[i+1][flag];
if(ret < solve(i,1)-lambda){
ret = solve(i,1)-lambda;
cnt[i][flag] = 1 + cnt[i][1];
}
else if(ret == solve(i,1)-lambda){
cnt[i][flag]=max(cnt[i][flag],1+cnt[i][1]);
}
}
else{
ret = a[i] + solve(i+1,1);
cnt[i][flag]=cnt[i+1][flag];
if(ret < a[i]+solve(i+1,0)){
ret=a[i]+solve(i+1,0);
cnt[i][flag] = cnt[i+1][0];
}
else if(ret==a[i]+solve(i+1,0)){
cnt[i][flag]=max(cnt[i][flag],cnt[i+1][0]);
}
}
return ret;
}
int main(){
scanf("%d%d",&n,&k);
forn(i,n) cin>>a[i];
ll l = 0, r = INF;
while(r>l){
ll mid = l+(r-l)/2;
lambda = mid;
memset(dp,-1,sizeof(dp));
solve(0,0);
if(cnt[0][0] <= k) r=mid;
else l=mid+1;
}
lambda = r;
memset(dp,-1,sizeof(dp));
solve(0,0);
ll ans = dp[0][0] + k * lambda;
printf("%lld\n", ans);
return 0;
}
