/**
* 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 <= 300;
}
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, pref[i] - pref[z]));
}
}
}
dp.swap(ndp);
}
cout << dp[n] << '\n';
}
} // namespace brute
struct Line {
int64_t a, b;
const static int64_t INF_LL = 0x3f3f3f3f3f3f3f3f;
Line(int64_t _a = 0, int64_t _b = INF_LL): a(_a), b(_b) {}
int64_t get(int64_t x) {
return (int64_t) a * x + b;
}
pair<int64_t, int64_t > intersect(const Line &other) {
return {other.b - b, a - other.a};
}
};
struct CHT {
int sz;
vector<Line> lines;
CHT(): sz(0) {}
bool can_remove_last(const Line &line) {
auto [x1, y1] = lines[sz - 2].intersect(line);
auto [x2, y2] = lines[sz - 1].intersect(line);
return (__int128_t) x1 * y2 <= (__int128_t) x2 * y1;
}
void add_line(const Line &new_line) {
while (sz >= 2 && can_remove_last(new_line)) {
lines.pop_back();
--sz;
}
lines.emplace_back(new_line);
++sz;
}
long long get_min(long long x) {
int low = 0, high = sz - 1;
while (low < high) {
int mid = low + (high - low + 1) / 2;
if (lines[mid].get(x) > lines[mid + 1].get(x)) {
low = mid;
} else {
high = mid - 1;
}
}
return lines[high].get(x);
}
};
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;
long long max_f = dp[0] - pref[0];
int max_f_min_seg = 0;
for (int i = 1; i <= n; ++i) {
dp[i] = dp[i - 1];
min_seg[i] = min_seg[i - 1];
long long nval = max_f + pref[i] + lambda;
if (nval > dp[i]) {
dp[i] = nval;
min_seg[i] = max_f_min_seg + 1;
} else if (nval == dp[i]) {
min_seg[i] = min(min_seg[i], max_f_min_seg + 1);
}
if (dp[i] - pref[i] > max_f) {
max_f = dp[i] - pref[i];
max_f_min_seg = min_seg[i];
} else if (dp[i] - pref[i] == max_f) {
max_f_min_seg = min(max_f_min_seg, min_seg[i]);
}
}
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;
}
