#include <bits/stdc++.h>
#define task "testing"
#define ll long long
#define multitest 0
using namespace std;
struct Node {
ll res, pre, suf, sm;
int resl, resr, prer, sufl, l, r;
};
const int N = 3e5;
bool lz[4*N+5];
Node mx[4*N+5], mn[4*N+5];
Node merge(Node u, Node v) {
Node res;
res.sm = u.sm+v.sm, res.l = u.l, res.r = v.r;
res.pre = max(u.pre, u.sm+v.pre);
if (res.pre == u.pre) {
res.prer = u.prer;
}
else {
res.prer = v.prer;
}
res.suf = max(u.suf+v.sm, v.suf);
if (res.suf == v.suf) {
res.sufl = v.sufl;
}
else {
res.sufl = u.sufl;
}
res.res = max({u.res, v.res, u.suf+v.pre});
if (res.res == u.res) {
res.resl = u.resl, res.resr = u.resr;
}
else if (res.res == v.res) {
res.resl = v.resl, res.resr = v.resr;
}
else {
res.resl = u.sufl, res.resr = v.prer;
}
return res;
}
void push(int nd, int lf, int rt) {
if (lz[nd]) {
swap(mx[nd], mn[nd]);
if (lf != rt) {
lz[nd*2] ^= lz[nd], lz[nd*2+1] ^= lz[nd];
}
lz[nd] = 0;
}
}
void upd(int nd, int lf, int rt, int p, ll v) {
if (p < lf || rt < p) return;
if (lf == rt) {
mx[nd].sm = v, mx[nd].l = mx[nd].r = p;
if (v >= 0) {
mx[nd].res = mx[nd].pre = mx[nd].suf = v;
mx[nd].resl = mx[nd].resr = mx[nd].prer = mx[nd].sufl = p;
}
else {
mx[nd].res = mx[nd].pre = mx[nd].suf = 0;
mx[nd].resl = mx[nd].resr = mx[nd].prer = mx[nd].sufl = -1;
}
mn[nd].sm = -v, mn[nd].l = mn[nd].r = p;
if (v <= 0) {
mn[nd].res = mn[nd].pre = mn[nd].suf = -v;
mn[nd].resl = mn[nd].resr = mn[nd].prer = mn[nd].sufl = p;
}
else {
mn[nd].res = mn[nd].pre = mn[nd].suf = 0;
mn[nd].resl = mn[nd].resr = mn[nd].prer = mn[nd].sufl = -1;
}
return;
}
int mid = (lf+rt)/2;
upd(nd*2, lf, mid, p, v);
upd(nd*2+1, mid+1, rt, p, v);
mx[nd] = merge(mx[nd*2], mx[nd*2+1]);
mn[nd] = merge(mn[nd*2], mn[nd*2+1]);
}
void flip(int nd, int lf, int rt, int l, int r) {
push(nd, lf, rt);
if (r < lf || rt < l) return;
if (l <= lf && rt <= r) {
swap(mx[nd], mn[nd]);
if (lf != rt) {
lz[nd*2] ^= 1, lz[nd*2+1] ^= 1;
}
return;
}
int mid = (lf+rt)/2;
flip(nd*2, lf, mid, l, r);
flip(nd*2+1, mid+1, rt, l, r);
mx[nd] = merge(mx[nd*2], mx[nd*2+1]);
mn[nd] = merge(mn[nd*2], mn[nd*2+1]);
}
void flo(int ID) {
int n, m; cin >> n >> m;
for (int x = 1; x <= n; x++) {
ll v; cin >> v;
upd(1, 1, n, x, v);
}
ll ans = 0, s = 0;
while (m--) {
ans = max(ans, s += mx[1].res);
flip(1, 1, n, mx[1].resl, mx[1].resr);
}
cout << ans << "\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
int TCS = 1, ID = 1;
if (multitest) {
cin >> TCS;
}
while (TCS--) flo(ID++);
return 0;
}
