#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(nullptr); cout.tie(nullptr);
int n, k;
cin >> n >> k;
vector<int> a(n + 1, 0);
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
auto combine = [&](const pair<int, int> &left, const pair<int, int> &right) -> pair<int, int> {
return {left.first + right.first, left.second + right.second};
};
auto f = [&](int x) -> pair<int, int> {
vector<vector<pair<int, int>>> dp(n + 1, vector<pair<int, int>> (2, {0, 0}));
dp[1][1] = {a[1] - x, 1};
for(int i = 2; i <= n; ++i){
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = max(combine(dp[i - 1][1], {a[i], 0}),
combine(dp[i - 1][0], {a[i] - x, 1}));
}
return max(dp[n][0], dp[n][1]);
};
int st = 0, en = 1e18, ans = 0;
while(st <= en){
int mid = st + (en - st) / 2;
if(f(mid).second >= k){
ans = mid;
st = mid + 1;
}else{
en = mid - 1;
}
}
auto [x, y] = f(ans);
cout << x + y * ans << "\n";
return 0;
}
