#include <bits/stdc++.h> using namespace std; using ll = long long; const ll inf = 1e18; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, k; cin>>n>>k; vector<int> a(n+1); vector<ll> pref(n+1); for (int i = 1; i<=n; i++) { cin>>a[i]; pref[i] = pref[i-1] + a[i]; } auto f = [&] (ll lambda) -> pair<ll, int> { vector<int> cnt(n+1, n+1); vector<ll> dp(n+1, -inf); cnt[0] = dp[0] = 0; priority_queue<pair<ll, int>> q; q.push({0, 0}); for (int i = 1; i<=n; i++){ auto [x, c] = q.top(); c*=-1; dp[i] = x + pref[i] - lambda; cnt[i] = c+1; if (dp[i-1]>dp[i] || (dp[i-1]==dp[i] && cnt[i-1]<cnt[i])) { dp[i] = dp[i-1]; cnt[i] = cnt[i-1]; } q.push({dp[i]-pref[i], -cnt[i]}); } return {dp[n], cnt[n]}; }; ll l = 0, r = 1e12; while(r-l>1){ ll mid = (l+r)/2; auto [x, y] = f(mid); if (y<=k) r = mid; else l = mid; } auto [x, y] = f(r); cout<<x+r*y; }