#include <bits/stdc++.h>
#define f first
#define s second
#define ll long long
#define pb push_back
#define all(v) v.begin(),v.end()
#define ld long double
using namespace std;
void data() {
#ifdef NURS
freopen("main.in", "r", stdin);
freopen("main.out", "w", stdout);
#endif
}
void win()
{
ios_base::sync_with_stdio(0),
cin.tie(0),cout.tie(0);
}
int block = 400;
const ld eps = 1e-6;
const int N = 1e6 + 500;
const int mod = 1e9 + 7;
const ll hh = 100010683;
const ll hh2 = 150005819;
int n, k, g, pos;
ll a[N];
ll s, ans;
ll dp[5000][5000], dp2[5000][5000], pref[5000];
int main()
{
data();
win();
cin >> n >> k;
bool was = 0;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
was = was | (a[i] < 0), s += a[i];
if (a[i] < 0)
g++, pos = i;
pref[i] += pref[i - 1] + a[i];
}
//first subtask
if (was == 0)
{
cout << s << '\n';
return 0;
}
//second subtask
if (g == 1 && k >= 2)
{
cout << s - a[pos] << '\n';
return 0;
}
else if (g == 1 && k == 1)
{
ans = max(ans, s);
s = 0;
for (int i = 1; i < pos; i++)
s += a[i];
ans = max(ans, s), s = 0;
for (int i = pos + 1; i <= n; i++)
s += a[i];
ans = max(ans, s);
cout << ans << '\n';
return 0;
}
//3 subtask
ll mn = 0;
for (int i = 1; i <= n; i++)
{
ans = max(ans, pref[i] - mn);
if (i == 1)
mn = pref[i];
else
mn = min(mn, pref[i]);
}
if (k == 1)
{
cout << ans;
return 0;
}
//4, 5 subtasks
if (n <= 300)
{
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= k; j++)
{
dp[i][j] = -1e9;
}
}
dp[0][0] = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= k; j++)
{
for (int len = 0; len <= i; len++)
{
if (dp[i - len][j - 1] != -1e9)
{
dp[i][j] = max(dp[i - len][j - 1] + pref[i] - pref[i - len], dp[i][j]);
}
}
dp[i][j] = max(dp[i][j], dp[i - 1][j]);
if (i == n && j == k)
ans = max(ans, dp[i][j]);
}
dp[i][0] = max(dp[i][0], dp[i - 1][0]);
}
cout << ans;
}
else
{
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= k; j++)
{
dp[i][j] = -1e9, dp2[i][j] = -1e9;;
}
}
dp[0][0] = 0, dp2[0][0] = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= k; j++)
{
dp[i][j] = max(dp[i][j], dp[i - 1][j] + a[i]);
dp[i][j] = max(dp[i][j], dp2[i - 1][j - 1] + a[i]);
dp2[i][j] = max(dp2[i - 1][j], dp2[i][j]);
dp2[i][j] = max(dp2[i][j], dp[i][j]);
ans = max(ans, dp2[i][j]);
ans = max(ans, dp[i][j]);
}
}
cout << ans;
}
}
