#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define ar array
const int INF = 1e15;
const int MOD = 1e9+7;
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
int n, k; cin>>n>>k;
vector<int> a(n);
for (int &i : a) cin>>i;
vector<int> pf(n+1);
pf[0] = 0; for (int i = 1; i <= n; i++) pf[i] = pf[i-1] + a[i-1];
int dp[n+1], cnt[n+1];
auto compute = [&](int lambda) {
dp[0] = cnt[0] = 0;
int besti = 0;
for (int i = 1; i <= n; i++) {
dp[i] = dp[i-1], cnt[i] = cnt[i-1];
if (dp[i] < dp[besti] + pf[i] - pf[besti] - lambda) {
dp[i] = dp[besti] + pf[i] - pf[besti] - lambda;
cnt[i] = cnt[besti] + 1;
}
if (dp[besti] - pf[besti] < dp[i] - pf[i]) besti = i;
}
};
int lo = 0, hi = 1e18, mid;
while (lo + 1 < hi) {
mid = (lo + hi) >> 1;
compute(mid);
if (cnt[n] <= k) {
hi = mid;
} else lo = mid+1;
}
compute(hi);
cout<<dp[n] + cnt[n]*hi<<"\n";
}
