/*
Author : kmv a.k.a kzhi
K41 IT CHV
*/
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define ll long long
#define FOR(i,a,b) for (int i = a ; i <= b; ++ i)
#define FOD(i,a,b) for (int i = a; i >= b; -- i)
#define BIT(mask,i) ((mask >> i) & 1)
#define MASK(i) (1ll << (i))
#define OFFBIT(mask,i) (mask &~(1ll<<(i)))
#define ONBIT(mask,i) (mask | (1ll << (i)))
#define lg2(x) (63 - __builtin_clzll(x))
#define c_bit __builtin_popcountll
#define vi vector < int >
#define all(a) a.begin(), a.end()
#define pb push_back
#define ii pair<int,int>
#define fi first
#define se second
#define openfile(TASK) if (fopen(TASK".inp","r"))\
{freopen(TASK".inp","r",stdin);freopen(TASK".out","w",stdout);}
#define endl '\n'
#define Faster ios_base::sync_with_stdio(false); \
cin.tie(0); cout.tie(0);
#define mid(l,r) ((l + r) >> 1)
#define left(id) (id << 1)
#define right(id) ((id << 1) | 1)
#define ci const int
template <class X, class Y> bool maximize(X &a, const Y &b){if(a < b) return a = b, true;return false;}
template <class X, class Y> bool minimize(X &a, const Y &b){if(a > b) return a = b, true;return false;}
const int N = 3e5 + 5;
const ll oo = 1e17 + 7;
const int LOG = lg2(N);
int n, k;
int a[N];
ll t[N];
ll sum(int l, int r){
if (l > r)
return 0;
return t[r] - t[l - 1];
}
bool ok1 = 1;
int cnt2 = 0, pos2 = -1;
namespace SUB1{
ll pt[N];
void SOLVE(){
pt[0] = oo;
ll res = - oo;
FOR (i, 1, n){
pt[i] = min(t[i], pt[i - 1]);
maximize(res, t[i] - pt[i - 1]);
maximize(res, t[i]);
}
maximize(res, 0ll);
cout << res;
}
}
namespace SUB6{
static const int maxN = 2e3 + 5;
ll dp[maxN][maxN][2];
ll sol(int i, int cnt, bool ok){
if (i == n + 1 || cnt == k + 1)
return 0;
if (dp[i][cnt][ok] != - oo)
return dp[i][cnt][ok];
ll cur = - oo;
if (!ok){
maximize(cur, sol(i + 1, cnt, 1) + a[i]);
maximize(cur, sol(i + 1, cnt, 0));
}
else{
maximize(cur, sol(i + 1, cnt, 1) + a[i]);
maximize(cur, sol(i + 1, cnt + 1, 0) + max(a[i], 0));
}
return dp[i][cnt][ok] = cur;
}
void SOLVE(){
FOR (i, 0, maxN - 1)
FOR (j, 0, maxN - 1)
FOR (ok, 0, 1)
dp[i][j][ok] = - oo;
cout << sol(1, 1, 0);
}
}
namespace FULL {
vector < ll > v;
ll s[N];
int par[N];
void build(){
FOR (i, 1, n){
par[i] = -1;
s[i] = a[i];
}
}
int F(int x){
if (par[x] < 0)
return x;
return par[x] = F(par[x]);
}
void Merge(int u, int v){
u = F(u);
v = F(v);
if (u == v)
return;
if (par[u] > par[v])
swap(u, v);
par[u] += par[v];
par[v] = u;
s[u] += s[v];
}
void SOLVE(){
build();
FOR (i, 1, n - 1)
if (a[i] >= 0 && a[i + 1] >= 0)
Merge(i, i + 1);
FOR (i, 1, n)
if (F(i) == i && a[i] >= 0)
v.pb(s[i]);
sort(all(v));
if (k >= v.size()){
ll res = 0;
for (ll i : v)
res += i;
cout << res;
}
else{
ll res = 0;
int sz = v.size();
FOR (i, 1, k)
res += v[sz - i];
cout << res;
}
}
}
void SOLVE(){
cin >> n >> k;
FOR (i, 1, n){
cin >> a[i];
t[i] = t[i - 1] + a[i];
if (a[i] < 0){
ok1 = 0;
cnt2 ++;
pos2 = i;
}
}
if (ok1){
cout << t[n];
return;
}
if (cnt2 == 1){
if (k >= 2)
cout << t[n] - a[pos2];
else
cout << max({t[n], sum(1, pos2 - 1), sum(pos2 + 1, n)});
return;
}
if (k == 1){
SUB1 :: SOLVE();
return;
}
if (n <= 2000 && k <= 2000){
SUB6 :: SOLVE();
return;
}
FULL :: SOLVE();
}
signed main(){
Faster
openfile("feast")
int q = 1;
// cin >> q;
while (q --){
SOLVE();
}
return 0;
}
