#include <bits/stdc++.h>
using namespace std;
#define N 500005
const int inf = INT_MAX;
const int M = 998244353;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int tc = 1, n, a[N], k, sum, dp[2001][2001], ans;
deque <int> d = {0};
signed main() {
ios::sync_with_stdio(0);cin.tie(0);
cin >> n >> k;
for(int i = 1; i <= n; i++) {
cin >> a[i];
int ok1 = (a[i] >= 0);
int ok2 = (sum >= 0);
if(ok1 == ok2) {
sum += a[i];
}
else {
d.push_back(sum);
sum = a[i];
}
ans = max(ans,sum);
}
d.push_back(sum);
n = (int)d.size() - 1;
for(int i = 1; i <= n; i++) {
dp[i][1] = max(d[i], dp[i - 1][1]);
}
for(int i = 1; i <= n; i++) {
for(int j = 2; j <= min(i,k); j++) {
dp[i][j] = dp[i - 1][j];
int sum = 0;
for(int l = i; l >= j; l--) {
sum += d[l];
dp[i][j] = max(dp[i][j],dp[l - 1][j - 1] + sum);
}
ans = max(ans, dp[i][j]);
}
}
cout << ans << '\n';
return 0;
}
