#ifdef EZ
#include "./ez/ez.h"
#else
#include <bits/stdc++.h>
#endif
#define mp make_pair
#define ll long long
#define pb push_back
#define fi first
#define se second
using namespace std;
void EZinit() {
#ifndef EZ
cin.tie(0)->sync_with_stdio(0);
#else
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
}
/*
vom afla raspunsul secvential: j=1,2,..k secvente. pt j=1 folosim cea mai mare subsecventa initial.
pt a trece de la j-1 la j, ori folosim o noua subsecventa, ori
spargem o subsecventa deja folosita (scoatem sub-subsecventa de suma MINIMA).
*/
void get(int &x)
{
static char c;
static bool neg;
while (!isdigit(c = getchar_unlocked()) && c != '-');
if (c == '-') neg = 1, x = 0;
else neg = 0, x = c-'0';
while (isdigit(c = getchar_unlocked())) x = x*10 + c-'0';
if (neg) x *= -1;
}
int n, k;
int v[300001];
ll sp[300001];
#define sum(x,y) (sp[y]-sp[x-1])
struct alexaint {
int x, y, xp, xs;
};
alexaint aintmi[1200001], aintma[1200001];
alexaint combine(alexaint A, alexaint B, int st, int dr, bool minmax)
{
alexaint Q; ll a, b, c;
a = sum(st, A.xp); b = sum(st, B.xp);
Q.xp = (((minmax) ? (a<=b) : (a>=b)) ? A.xp : B.xp);
a = sum(B.xs, dr); b = sum(A.xs, dr);
Q.xs = (((minmax) ? (a<=b) : (a>=b)) ? B.xs : A.xs);
a = sum(A.x, A.y); b = sum(B.x, B.y); c = sum(A.xs, B.xp);
if (minmax)
{
if (a <= min(b,c)) Q.x = A.x, Q.y = A.y;
else if (b <= min(a,c)) Q.x = B.x, Q.y = B.y;
else Q.x = A.xs, Q.y = B.xp;
}
else
{
if (a >= max(b,c)) Q.x = A.x, Q.y = A.y;
else if (b >= max(a,c)) Q.x = B.x, Q.y = B.y;
else Q.x = A.xs, Q.y = B.xp;
}
return Q;
}
void build(int nod = 1, int st = 1, int dr = n)
{
if (st == dr) return (void) (aintma[nod] = aintmi[nod] = {st, st, st, st});
int mj = st+dr >> 1;
build(nod*2, st, mj);
build(nod*2+1, mj+1, dr);
aintma[nod] = combine(aintma[nod*2], aintma[nod*2+1], st, dr, false);
aintmi[nod] = combine(aintmi[nod*2], aintmi[nod*2+1], st, dr, true);
}
alexaint que(int qst, int qdr, bool minmax, alexaint aint[], int nod = 1, int st = 1, int dr = n)
{
if (qst <= st && dr <= qdr) return aint[nod];
int mj = st+dr >> 1;
if (qst <= mj && mj < qdr)
{
alexaint q1 = que(qst, qdr, minmax, aint, nod*2, st, mj);
alexaint q2 = que(qst, qdr, minmax, aint, nod*2+1, mj+1, dr);
return combine(q1, q2, qst, qdr, minmax);
}
else if (qst <= mj) return que(qst, qdr, minmax, aint, nod*2, st, mj);
else return que(qst, qdr, minmax, aint, nod*2+1, mj+1, dr);
}
struct alexmax {
int fi, se;
bool operator<(const alexmax &B) const
{
auto Xq = que(fi, se, false, aintma);
int X1 = Xq.x, X2 = Xq.y;
auto Yq = que(B.fi, B.se, false, aintma);
int Y1 = Yq.x, Y2 = Yq.y;
return sp[X2]-sp[X1-1] < sp[Y2]-sp[Y1-1];
}
};
struct alexmin {
int fi, se;
bool operator<(const alexmin &B) const
{
auto Xq = que(fi, se, true, aintmi);
int X1 = Xq.x, X2 = Xq.y;
auto Yq = que(B.fi, B.se, true, aintmi);
int Y1 = Yq.x, Y2 = Yq.y;
return sp[X2]-sp[X1-1] > sp[Y2]-sp[Y1-1];
}
};
int main()
{
EZinit();
get(n); get(k);
for (int i = 1; i <= n; ++i) get(v[i]), sp[i] = sp[i-1] + v[i];
build();
ll ans = 0;
priority_queue<alexmin> ivuse;
priority_queue<alexmax> ivno;
ivno.push({1, n});
for (int j = 1; j <= k; ++j)
{
// ce putem scoate
ll Ss = LLONG_MAX; int xs, ys, Xs, Ys;
if (!ivuse.empty())
{
xs = ivuse.top().fi, ys = ivuse.top().se;
auto q = que(xs, ys, true, aintmi);
Xs = q.x, Ys = q.y;
Ss = sp[Ys]-sp[Xs-1];
if (-Ss <= 0) ivuse.pop();
}
// ce putem pune
ll Sp = LLONG_MIN; int xp, yp, Xp, Yp;
if (!ivno.empty())
{
xp = ivno.top().fi, yp = ivno.top().se;
auto q = que(xp, yp, false, aintma);
Xp = q.x, Yp = q.y;
Sp = sp[Yp]-sp[Xp-1];
if (Sp <= 0) ivno.pop();
}
if (Ss != LLONG_MAX && -Ss >= 1 && (-Ss > Sp || Sp == LLONG_MIN))
{ // scoatem
ivuse.pop();
if (xs != Xs) ivuse.push({xs,Xs-1});
if (ys != Ys) ivuse.push({Ys+1, ys});
ivno.push({Xs,Ys});
ans += -Ss;
}
if (Sp != LLONG_MIN && Sp >= 1 && (Sp >= -Ss || Ss == LLONG_MAX))
{ // punem
ivno.pop();
if (xp != Xp) ivno.push({xp,Xp-1});
if (yp != Yp) ivno.push({Yp+1, yp});
ivuse.push({Xp,Yp});
ans += Sp;
}
}
cout << ans << '\n';
}
