/**
* author minhnguyent546
* created_at Sun, 2025-01-26 08:09:26
* problem https://oj.uz/problem/view/NOI19_feast
**/
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "cp/debug.h"
#else
#define debug(...)
#define cerr if (false) cerr
#endif
int n, k;
vector<int> arr;
vector<long long> pref;
void read() {
cin >> n >> k;
arr.resize(n);
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
pref.resize(n + 1);
for (int i = 0; i < n; ++i) {
pref[i + 1] = pref[i] + arr[i];
}
}
long long sum(int l, int r) {
assert(0 <= l && l <= r && r < n);
return pref[r + 1] - pref[l];
}
const long long INF_LL = 0x3f3f3f3f3f3f3f3f;
namespace brute {
bool check() {
return n <= 2000;
}
void solve() {
cerr << " *** [BRUTE] *** " << '\n';
vector<long long> dp(n + 1, -INF_LL);
vector<long long> ndp(n + 1);
dp[0] = 0;
for (int j = 0; j <= k; ++j) {
for (int i = 1; i <= n; ++i) {
ndp[i] = ndp[i - 1];
if (j > 0) {
for (int z = 0; z < i; ++z) {
ndp[i] = max(ndp[i], dp[z] + max(0LL, sum(z, i - 1)));
}
}
}
dp.swap(ndp);
}
cout << dp[n] << '\n';
}
} // namespace brute
namespace sub7 {
bool check() {
return true;
}
void solve() {
cerr << " *** [SUB 7] *** " << '\n';
long long low = -(long long) 1e18, high = 0;
vector<long long> dp(n + 1);
vector<int> min_seg(n + 1);
auto gud = [&](long long lambda) -> bool {
fill(dp.begin(), dp.end(), -INF_LL);
dp[0] = 0;
min_seg[0] = 0;
for (int i = 1; i <= n; ++i) {
dp[i] = dp[i - 1];
min_seg[i] = min_seg[i - 1];
for (int z = 0; z < i; ++z) {
long long cost = sum(z, i - 1) + lambda;
long long nval = dp[z] + cost;
if (nval > dp[i]) {
dp[i] = nval;
min_seg[i] = min_seg[z] + 1;
} else if (nval == dp[i]) {
min_seg[i] = min(min_seg[i], min_seg[z] + 1);
}
}
}
// cerr << "lambda = " << lambda << ", min_seg[n] = " << min_seg[n] << ", dp[n] = " << dp[n] << '\n';
return min_seg[n] <= k;
};
while (low < high) {
long long mid = low + (high - low + 1) / 2;
if (gud(mid)) {
low = mid;
} else {
high = mid - 1;
}
}
long long lambda = high;
gud(lambda);
long long ans = dp[n] - lambda * k;
cout << ans << '\n';
}
} // namespace sub7
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin.exceptions(cin.failbit);
read();
#ifdef LOCAL
sub7::solve(); return 0;
brute::solve(); return 0;
#endif
if (brute::check()) {
brute::solve(); return 0;
}
if (sub7::check()) {
sub7::solve(); return 0;
}
assert(false);
return 0;
}
