#include "bits/stdc++.h"
using namespace std;
# define int long long
# define all(a) a.begin(), a.end()
vector<int> a;
int n, k;
using int128_t = __int128_t;
const int128_t INF = 1e36;
vector<vector<pair<int128_t, int128_t>>> dp;
pair<int128_t, int128_t> check(int128_t x){
dp.assign(n + 1, vector<pair<int128_t, int128_t>>(2, {-INF, 0}));
dp[0][1] = {0, 0};
for(int i = 1; i <= n; ++i){
auto t1 = make_pair(dp[i - 1][0].first + a[i - 1], dp[i - 1][0].second);
auto t2 = make_pair(dp[i - 1][1].first + x + a[i - 1], dp[i - 1][1].second - 1);
dp[i][0] = max(t1, t2);
dp[i][1] = max(dp[i - 1][0], dp[i - 1][1]);
}
return max(dp[n][0], dp[n][1]);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
cin >> n >> k;
a.resize(n);
for(auto &i : a) cin >> i;
int128_t l = -1e18, r = 1;
while(r - l > 1){
int m = (r + l) / 2;
if(-check(m).second >= k){
r = m;
} else {
l = m;
}
}
auto ans = check(r);
ans.second = -ans.second;
// cerr << (int)ans.second << '\n';
cout << (int)(ans.first - r * ans.second) << '\n';
return 0;
}
