#include <bits/stdc++.h>
using ll = long long;
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];
for (int i = 1; i < n; i++) {
pref[i] = pref[i - 1] + a[i];
if (pref[i] < pref[i - 1]) {
minpref[i] = i;
} else {
minpref[i] = minpref[i - 1];
}
}
ll maxval = 0;
for (int i = 0; i < n; i++) {
ll sum = pref[i] - minpref[i];
if (sum > maxval) {
maxval = sum;
}
dp[i][1] = maxval;
}
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 = dp[add][j - 1];
up = max(up, addval + dp[i][j - 1]);
dp[i][j] = up;
}
}
cout << dp[n - 1][k];
}
