#include <bits/stdc++.h>
using ll = int;
using namespace std;
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
ll n, k;
cin >> n >> k;
vector<ll> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<vector<ll>> dp(n, vector<ll>(k + 1));
vector<ll> pref(n);
vector<ll> minpref(n);
pref[0] = a[0];
ll minn = a[0];
for (int i = 1; i < n; i++) {
pref[i] = pref[i - 1] + a[i];
if (pref[i] < minn) {
minpref[i] = i;
} else {
minpref[i] = minpref[i - 1];
}
}
minn = 0;
ll count = 0;
ll maxcount = 0;
for (int i = 0; i < n; i++) {
count = pref[i] - minn;
if (count > maxcount) {
maxcount = count;
}
minn = min(minn, pref[i]);
dp[i][1] = maxcount;
}
for (int i = 0; i < k; i++) {
if (a[0] > 0) {
dp[0][i] = a[i];
} else
dp[0][i] = 0;
}
for (int i = 1; i < n; i++) {
for (int j = 2; j <= k; j++) {
ll up = dp[i][j];
up = max(up, dp[i - 1][j]);
up = max(up, dp[i][j - 1]);
up = max(up, dp[i][j - 1] + a[i]);
ll add = minpref[i];
ll addval;
if (add != 0) {
add = add - 1;
addval = dp[add][j - 1];
} else {
addval = 0;
}
up = max(up, addval + dp[i][j - 1]);
dp[i][j] = up;
}
}
cout << dp[n - 1][k];
}
