#include <cstdio>
#include <climits>
#include <functional>
#include <numeric>
#include <cstring>
#include <cassert>
#include <string>
#include <deque>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
#include <utility>
using namespace std;
using ll=long long;
#define N 300005
#define ALL(x) x.begin(), x.end()
int n, k, a[N];
long long p[N];
int main()
{
cin.tie(0)->sync_with_stdio(0);
cin >> n >> k;
for (int i = 1; i <= n; ++i) cin >> a[i], p[i] = p[i-1] + a[i];
if (count_if(a+1, a+1+n,[](int x){ return x<0; }) == 0) return cout << accumulate(a+1,a+1+n, 0ll), 0;
if (count_if(a+1, a+1+n,[](int x){ return x<0; }) == 1)
{
int x=0;
for (int i = 1; i <= n; ++i) if (a[i] < 0) x = i;
if (k == 1) return cout << max({p[x-1], p[n] - p[x], p[n]}), 0;
else return cout << p[n] - a[x], 0;
}
if (k == 1)
{
long long ans = 0, mn = 0;
for (int i = 1; i <= n; ++i) ans = max(ans, p[i] - mn), mn = min(mn, p[i]);
return cout << ans, 0;
}
if (n <= 3000)
{
vector<vector<vector<long long>>> dp(2, vector<vector<long long>>(3005, vector<long long>(2)));
long long ans = 0;
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= k; ++i)
{
dp[i&1][j][0] = max(dp[!(i&1)][j][0], dp[!(i&1)][j][1]);
dp[i&1][j][1] = max({a[i] + dp[!(i&1)][j-1][0], a[i] + dp[!(i&1)][j][1]});
ans = max({ans, dp[i&1][j][0], dp[i&1][j][1]});
}
}
return cout << ans, 0;
}
if (n <= 300)
{
long long dp[305][305]{0};
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= k; ++j)
{
dp[i][j] = max({dp[i-1][j], dp[i][j], dp[i][j-1]});
for (int l = 0; l < i; ++l) dp[i][j] = max(dp[i][j], dp[l][j-1] + p[i] - p[l]);
}
return cout << dp[n][k], 0;
}
assert(0);
#if 0
{
function<void(int, int, int, int, int)> compute = [&](int i, int l, int r, int optl, int optr)
{
if (l > r) return;
int m = (l+r)/2;
pair<long long, int> best = {LLONG_MIN, -1};
for (int k = optl; k <= min(m, optr); ++k)
best = max(best, {(dp[!(i&1)][k]) + p[m] - p[k], k});
dp[i&1][m] = best.first;
compute(i, l, m-1, optl, best.second), compute(i, m+1, r, best.second, optr);
};
long long ans = 0;
for (int i = 1; i <= k; ++i)
{
compute(i, 1, n, 0, n-1);
for (int i = 1; i <= n; ++i) dp[i&1][i] = max(dp[i&1][i], dp[i&1][i-1]);
ans = max(ans, *max_element(dp[i&1], dp[i&1]+n+1));
}
return cout << ans,0;
}
#endif
return 0;
}
