// Programmer: Shadow1
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using str = string; // yay python!
#define i64 int64_t
#define show(x) cerr << (#x) << " = " << (x) << '\n';
#define output_vector(v) for(auto &x : v){cout << x << ' ';}cout << '\n';
#define output_pairvector(v) for(auto &x : v){cout << x.first << " " << x.second << '\n';}
#define read_vector(v) for(auto &x : v){cin >> x;}
#define vt vector
#define prq priority_queue
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define fir first
#define sec second
#define sz(x) ll(x.size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define int long long
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
//
//
void solve() {
int n, k;
cin >> n >> k;
vector<int> a(n+1), p(n+1);
bool pos = true;
for(int i=1; i<=n; ++i) {
cin >> a[i];
if(a[i] < 0) pos = false;
p[i] = p[i-1] + a[i];
}
int ans = 0;
if(pos) {
for(auto &A : a) ans += A;
cout << ans << '\n';
return;
}
int dp[n+1][k+1];
memset(dp, 0, sizeof(dp));
vector<priority_queue<int>> pq(k+1);
for(int i=0; i<=k; ++i)
pq[i].push(0);
for(int i=1; i<=n; ++i) {
for(int j=0; j<=min(i, k); ++j) {
dp[i][j] = dp[i-1][j];
if(j > 0) {
dp[i][j] = max(dp[i-1][j], pq[j-1].top() + p[i]);
}
pq[j].push(dp[i][j] - p[i]);
}
}
cout << dp[n][k] << '\n';
}
// CHECK YOUR OVERFLOWS!!!!
signed main() {
// freopen("output.txt", "w", stdout);
// freopen("input.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(NULL);
int T = 1;
// cin >> T;
for(int tc = 1; tc <= T; ++tc) {
// cout << "Case #" << tc << ": ";
solve();
}
return 0;
}
