#include <bits/stdc++.h>
using namespace std; using ll = long long; const int N = 300005;
int n, k, a[N];
ll p[N], bit[N], dp[2002][2020];
void up(int id, ll val) {
while(id <= n) bit[id] = max(bit[id], val), id += -id&id;
}
ll MAX(int id) {
ll res = 0;
while(id > 0) res = max(res, bit[id]), id -= -id&id;
return res;
}
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> k;
int mn = (int)2e9, dem = 0;
for(int i=1;i<=n;++i) cin >> a[i], p[i] = p[i-1] + a[i], mn = min(mn, a[i]), dem += (a[i] < 0);
if(mn >= 0) {
cout << p[n]; return 0;
}
if(k == 1) {
ll MIN = 0, ans = 0;
for(int i=1;i<=n;++i) ans = max(ans, p[i] - MIN), MIN = min(MIN, p[i]);
cout << ans;return 0;
}
if(dem == 1) {
ll ans = 0;
for(int i=1;i<=n;++i) ans += max(a[i], 0);
cout << ans;return 0;
}
for(int j=1;j<=k;++j) {
fill(bit,bit+n+1,0);
for(int i=1;i<=n;++i)
up(i,dp[i][j-1] - p[i]), dp[i][j] = max(dp[i-1][j], p[i] + MAX(i));
}
cout << dp[n][k];
return 0;
}
