#include <bits/stdc++.h> using namespace std; using ll = long long; pair<ll, int> best(pair<ll, int> L, pair<ll, int> R) { if (L.first == R.first) return {L.first, min(L.second, R.second)}; return max(L, R); } int main() { ios::sync_with_stdio(false); cin.tie(0); int n, k; cin>>n>>k; vector<ll> a(n+1); for (int i = 1; i<=n; i++) cin>>a[i]; auto f = [&] (ll x) -> pair<ll, int> { vector<vector<pair<ll, int>>> dp(n+1, vector<pair<ll, int>>(2)); dp[0][0] = {0, 0}; dp[0][1] = {-1e18, 0}; for (int i = 1; i<=n; i++){ dp[i][0] = best(dp[i-1][0], dp[i-1][1]); dp[i][1] = dp[i-1][1]; dp[i][1].first += a[i]; if (dp[i-1][0].first > dp[i][1].first || (dp[i-1][0].first == dp[i][1].first && dp[i-1][0].second<dp[i][1].second)) { dp[i][1] = dp[i-1][0]; dp[i][1].first += a[i]-x; dp[i][1].second++; } } return best(dp[n][0], dp[n][1]); }; ll l = 0, r = 1e9; while(r-l>1){ ll mid = (l+r)/2; auto p = f(mid); if (p.second >= k) l = mid; else r = mid; } auto p = f(l); cout<<p.first+p.second*l; }