#include <bits/stdc++.h>
using namespace std;
#define int long long
constexpr int N = 2005;
int dp[N][N][2], a[N];
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int cnt = 0;
for (int i = 1; i <= n; i++) {
if (a[i] < 0) {
cnt++;
}
}
if (k == 1 || cnt == 0) {
int ans = 0, sum = 0;
for (int i = 1; i <= n; i++) {
sum += a[i];
if (sum < 0) {
sum = 0;
}
ans = max(ans, sum);
}
cout << ans << '\n';
} else if (cnt == 1) {
int left = 0, right = 0;
for (int i = 1; i <= n; i++) {
if (a[i] < 0) break;
left += a[i];
}
for (int i = n; i >= 1; i--) {
if (a[i] < 0) break;
right += a[i];
}
cout << left + right << '\n';
} else {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k; j++) {
dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1]);
dp[i][j][1] = max(dp[i - 1][j][1] + a[i], dp[i - 1][j - 1][0] + a[i]);
}
}
cout << max(dp[n][k][0], dp[n][k][1]) << '\n';
}
return 0;
}
