#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 3e5 + 11;
int a[MAXN], dp[MAXN], dp2[MAXN], c[MAXN], c2[MAXN];
int32_t main(){
int n, k; cin >> n >> k;
for(int i = 0; i < n; i++){
cin >> a[i];
}
auto test = [&n](int C) {
fill(dp, dp + MAXN, -(1LL << 60));
fill(dp2, dp2 + MAXN, -(1LL << 60));
fill(c, c + MAXN, 0);
fill(c2, c2 + MAXN, 0);
dp[0] = -(1LL << 60), dp2[0] = 0;
for(int j = 0; j < n; j++){
if(dp2[j - 1] + a[j] - C >= dp[j] + a[j]){
dp[j + 1] = dp2[j - 1] + a[j] - C;
c[j + 1] = c2[j - 1] + 1;
}else{
dp[j + 1] = dp[j] + a[j];
c[j + 1] = c[j];
}
if(dp2[j] >= dp[j + 1]){
dp2[j + 1] = dp2[j];
c2[j + 1] = c2[j];
}else{
dp2[j + 1] = dp[j + 1];
c2[j + 1] = c[j + 1];
}
}
};
int l = 0, r = 1 << 30;
while(l + 1 != r){
int mid = (l + r) / 2;
test(mid);
if(c2[n] > k){
l = mid;
}else{
r = mid;
}
}
test(l); int v1 = dp2[n] + l * c2[n], k1 = c2[n];
test(r); int v2 = dp2[n] + r * c2[n], k2 = c2[n];
cout << v1 + (k1 != k2 ? (v2 - v1) / (k2 - k1) * (k - k1) : 0) << endl;
}
