#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Node {
ll sm = 0;
ll pre = 0, suf = 0, res = 0;
int l = 0, r = 0;
int pr = -1, sf = -1; // prefix right idx, suffix left idx
int rl = -1, rr = -1; // best subarray [rl,rr]
};
vector<Node> mx, mn;
vector<char> lz;
vector<ll> a;
Node make_leaf(ll val, int idx) {
Node X;
X.sm = val; X.l = X.r = idx;
if (val > 0) {
X.pre = X.suf = X.res = val;
X.pr = X.sf = X.rl = X.rr = idx;
} else {
X.pre = X.suf = X.res = 0;
X.pr = X.sf = X.rl = X.rr = -1;
}
return X;
}
Node mergeN(const Node &L, const Node &R) {
Node P;
P.sm = L.sm + R.sm;
P.l = L.l; P.r = R.r;
// prefix: choose between L.pre (idx L.pr) and L.sm + R.pre (idx R.pr)
ll cand_pre_val = 0; int cand_pre_idx = -1;
if (L.pr != -1) { cand_pre_val = L.pre; cand_pre_idx = L.pr; }
// second candidate
if (R.pr != -1) {
ll v2 = L.sm + R.pre;
if (v2 > cand_pre_val) { cand_pre_val = v2; cand_pre_idx = R.pr; }
}
P.pre = cand_pre_val; P.pr = cand_pre_idx;
// suffix: choose between R.suf (idx R.sf) and L.suf + R.sm (idx L.sf)
ll cand_suf_val = 0; int cand_suf_idx = -1;
if (R.sf != -1) { cand_suf_val = R.suf; cand_suf_idx = R.sf; }
if (L.sf != -1) {
ll v2 = L.suf + R.sm;
if (v2 > cand_suf_val) { cand_suf_val = v2; cand_suf_idx = L.sf; }
}
P.suf = cand_suf_val; P.sf = cand_suf_idx;
// res: three candidates: L.res (L.rl), R.res (R.rl), cross (L.suf + R.pre) if both sides valid
P.res = 0; P.rl = P.rr = -1;
if (L.rl != -1) { P.res = L.res; P.rl = L.rl; P.rr = L.rr; }
if (R.rl != -1 && R.res > P.res) { P.res = R.res; P.rl = R.rl; P.rr = R.rr; }
if (L.sf != -1 && R.pr != -1) {
ll cross = L.suf + R.pre;
if (cross > P.res) {
P.res = cross; P.rl = L.sf; P.rr = R.pr;
}
}
// If none positive, P.res stays 0 and rl=-1
return P;
}
void build(int nd, int l, int r) {
if (l == r) {
mx[nd] = make_leaf(a[l], l);
mn[nd] = make_leaf(-a[l], l);
return;
}
int mid = (l + r) >> 1;
build(nd<<1, l, mid);
build(nd<<1|1, mid+1, r);
mx[nd] = mergeN(mx[nd<<1], mx[nd<<1|1]);
mn[nd] = mergeN(mn[nd<<1], mn[nd<<1|1]);
}
void push(int nd, int l, int r) {
if (!lz[nd]) return;
swap(mx[nd], mn[nd]);
if (l != r) {
lz[nd<<1] ^= 1;
lz[nd<<1|1] ^= 1;
}
lz[nd] = 0;
}
void flip(int nd, int l, int r, int L, int R) {
push(nd, l, r);
if (R < l || r < L) return;
if (L <= l && r <= R) {
swap(mx[nd], mn[nd]);
if (l != r) { lz[nd<<1] ^= 1; lz[nd<<1|1] ^= 1; }
return;
}
int mid = (l + r) >> 1;
flip(nd<<1, l, mid, L, R);
flip(nd<<1|1, mid+1, r, L, R);
push(nd<<1, l, mid); push(nd<<1|1, mid+1, r);
mx[nd] = mergeN(mx[nd<<1], mx[nd<<1|1]);
mn[nd] = mergeN(mn[nd<<1], mn[nd<<1|1]);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
if (!(cin >> n >> m)) return 0;
a.assign(n+1, 0);
for (int i = 1; i <= n; ++i) cin >> a[i];
mx.assign(4*n+5, Node());
mn.assign(4*n+5, Node());
lz.assign(4*n+5, 0);
build(1, 1, n);
ll ans = 0, s = 0;
for (int it = 0; it < m; ++it) {
push(1, 1, n); // ensure root up-to-date
if (mx[1].rl == -1) break; // no positive subarray left
ll cur = mx[1].res;
s += cur;
ans = max(ans, s);
flip(1, 1, n, mx[1].rl, mx[1].rr);
}
cout << ans << '\n';
return 0;
}
