#include <iostream>
#include <algorithm>
#include <cstring>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ll long long
#define inf 1e18
using namespace std;
struct dt{
ll t, c;
bool operator < (const dt &x) const{
return (t > x.t);
}
};
const int N = 3e5 + 9;
int n, k, t, p;
ll dp[2009][2009], a[N], pre[N], res, cur;
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen("nhap.inp", "r", stdin);
// freopen("xuat.out", "w", stdout);
cin >> n >> k;
FOR(i, 1, n) {
cin >> a[i];
t += (a[i] < 0);
if (a[i] < 0) p = i;
pre[i] = pre[i-1] + a[i];
res = max(res, pre[i] - cur);
cur = min(cur, pre[i]);
}
if (t == 0){
cout << pre[n]; return 0;
}
if (k == 1) {
cout << res; return 0;
}
if (t == 1) {
cout << pre[n] - a[p];
return 0;
}
FOR(i, 1, k) {
ll cur = 0;
FOR(j, 1, n) {
cur = max(cur, dp[i-1][j] - pre[j]);
dp[i][j] = max(dp[i][j-1], pre[j] + cur);
}
}
cout <<dp[k][n];
return 0;
}
