#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 allNonNeg = true;
long long totalSum = 0;
for (int i = 1; i <= n; i++) {
if (a[i] < 0) allNonNeg = false;
totalSum += a[i];
}
if (allNonNeg) {
cout << totalSum << endl;
return 0;
}
int negCount = 0;
for (int i = 1; i <= n; i++) {
if (a[i] < 0) negCount++;
}
if (negCount <= 1) {
long long sumLeft = 0, sumRight = 0;
int negPos = -1;
for (int i = 1; i <= n; i++) {
if (a[i] < 0) { negPos = i; break; }
}
if (negPos == -1) {
cout << totalSum << endl;
return 0;
}
for (int i = 1; i < negPos; i++) sumLeft += a[i];
for (int i = negPos + 1; i <= n; i++) sumRight += a[i];
long long ans = 0;
ans = max(ans, sumLeft);
ans = max(ans, sumRight);
ans = max(ans, totalSum);
ans = max(ans, sumLeft + sumRight);
if (k == 1) {
ans = max({(long long)0, sumLeft, sumRight, totalSum});
} else {
ans = max({(long long)0, sumLeft, sumRight, totalSum, sumLeft + sumRight});
}
cout << ans << endl;
return 0;
}
const long long NEG_INF = LLONG_MIN / 2;
vector<long long> f(k + 1, 0);
vector<long long> g(k + 1, NEG_INF);
for (int i = 1; i <= n; i++) {
vector<long long> f_prev = f;
for (int j = 1; j <= k; j++) {
long long extend;
if (g[j] == NEG_INF) {
extend = NEG_INF;
} else {
extend = g[j] + a[i];
}
long long start;
if (f_prev[j-1] == NEG_INF) {
start = NEG_INF;
} else {
start = f_prev[j-1] + a[i];
}
g[j] = max(extend, start);
f[j] = max(f_prev[j], g[j]);
}
}
cout << f[k] << endl;
return 0;
}
