#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
#define pb push_back
#define fi first
#define se second
const ll N = 2003;
ll n,k,sum,b[N];
ll mins,pos,idx;
vector<ll> a;
ll memo[N][N][2];
ll dp(ll x, ll y, ll stat) {
if(x == idx+1) return 0;
ll tmp = memo[x][y][stat];
if(tmp != -1) return tmp;
if(stat == 0) {
tmp = dp(x+1,y,0);
if(y > 0) {
tmp = max(tmp,dp(x+1,y-1,1)+a[x]);
}
}
else {
tmp = max(dp(x+1,y,0),dp(x+1,y,1)+a[x]);
}
return memo[x][y][stat] = tmp;
}
int main() {
memset(memo,-1,sizeof(memo));
cin >> n >> k;
for(int i=1; i<=n; i++) {
cin >> b[i];
}
a.pb(0);
for(int i=1; i<=n; i++) {
if(b[i] >= 0) {
sum += b[i];
if(mins < 0) {
a.pb(mins);
mins = 0;
}
}
else {
mins += b[i];
if(sum > 0) {
a.pb(sum);
sum = 0;
pos++;
}
}
}
if(sum > 0) {
a.pb(sum);
pos++;
}
if(mins < 0) a.pb(mins);
idx = a.size()-1;
cout << dp(1,k,0) << endl;
}
