#pragma GCC optimize("Os")
#include <bits/stdc++.h>
using namespace std;
const int MN = 2e6+5;
const int INF = 0x3f3f3f3f;
#define int long long
#define pb push_back
#define p make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define f(i,a,b) for (int i = a ; i < b ; i++)
#define f1(i,a,b) for (int i = a ; i > b ; i--)
#define f2(i,a,b) for (int i = a ; i <= b ; i++)
#define FILE(X) \
freopen(#X ".INP","r",stdin); \
freopen(#X ".OUT","w",stdout);
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int random(int l, int r) { return l + rd() % (r - l + 1); }
int a[MN];
int n,k,pos;
int cnt = 0;
int dp[5003][5003];
int pre[MN];
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//FILE(BLUESKY);
bool flag = false;
cin >> n >> k;
for (int i = 1 ; i <= n ; i++) {
cin >> a[i];
pre[i] = pre[i-1] + a[i];
if (a[i] < 0) flag = true,cnt++, pos = i;
}
if (flag == false) cout << accumulate(a+1,a+n+1,0LL);
else if (cnt == 1) {
if (k == 1) {
int sum = 0, sum2 = 0;
for (int i = 1 ; i < pos ; i++) sum += a[i];
for (int i = pos+1 ; i <= n ; i++) sum2 += a[i];
cout << max(sum,sum2) << "\n";
}
else {
cout << accumulate(a+1,a+n+1,0LL) - a[pos];
}
}
else if (cnt == n) cout << 0;
else if (n <= 5000) {
for (int i = 1; i <= k; ++i){
int cur = 0;
for (int j = 1; j <= n; ++j) {
cur = max(cur, dp[i-1][j] - pre[j]);
dp[i][j] = max(dp[i][j-1], cur + pre[j]);
}
}
cout << dp[k][n];
}
return 0;
}
