#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<long long> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
bool todop = true;
long long t = 0;
for (int i = 1; i <= n; i++) {
if (a[i] < 0) todop = false;
t += a[i];
}
if (todop) {
cout << t << endl;
return 0;
}
int ncount = 0;
for (int i = 1; i <= n; i++) {
if (a[i] < 0) ncount++;
}
if (ncount <= 1) {
long long sumi = 0, sumd = 0;
int negPos = -1;
for (int i = 1; i <= n; i++) {
if (a[i] < 0) { negPos = i; break; }
}
if (negPos == -1) {
cout << t << endl;
return 0;
}
for (int i = 1; i < negPos; i++) sumi += a[i];
for (int i = negPos + 1; i <= n; i++) sumd += a[i];
long long ans = 0;
ans = max(ans, sumi);
ans = max(ans, sumd);
ans = max(ans, t);
ans = max(ans, sumi + sumd);
if (k == 1) {
ans = max({(long long)0, sumi, sumd, t});
} else {
ans = max({(long long)0, sumi, sumd, t, sumi + sumd});
}
cout << ans << endl;
return 0;
}
const long long NI = LLONG_MIN / 2;
vector<long long> f(k + 1, 0);
vector<long long> g(k + 1, NI);
for (int i = 1; i <= n; i++) {
vector<long long> fp = f;
for (int j = 1; j <= k; j++) {
long long ex;
if (g[j] == NI) {
ex = NI;
} else {
ex = g[j] + a[i];
}
long long s;
if (fp[j-1] == NI) {
s = NI;
} else {
s = fp[j-1] + a[i];
}
g[j] = max(ex, s);
f[j] = max(fp[j], g[j]);
}
}
cout << f[k] << endl;
return 0;
}
