#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;
}
