#include <bits/stdc++.h> #define ii pair<int, int> #define fi first #define se second #define inf 0x3f3f3f3f3f3f3f3f using namespace std; using ll = long long; const ll mod=1e9+7; const int nx=3e5+5; int n, k, a[nx]; struct dak { ll sum, pre, suf, res; int pl, pr; ii pos; dak() { sum=0; pre=suf=res=-inf; pl=pr=-1; pos={-1, -1}; } } nod[nx<<2], st[nx<<2]; dak operator +(dak a, dak b) { dak c; c.sum=a.sum+b.sum; if(a.pre>a.sum+b.pre) c.pre=a.pre, c.pl=a.pl; else c.pre=a.sum+b.pre, c.pl=b.pl; if(b.suf>b.sum+a.suf) c.suf=b.suf, c.pr=b.pr; else c.suf=b.sum+a.suf, c.pr=a.pr; c.res=max(max(a.res, b.res), a.suf+b.pre); if(a.res==c.res) c.pos=a.pos; else if(b.res==c.res) c.pos=b.pos; else c.pos={a.pr, b.pl}; return c; } bool la[nx<<2]; void build(int id, int l, int r) { la[id]=0; if(l==r) { nod[id].sum=nod[id].pre=nod[id].suf=nod[id].res=a[l]; nod[id].pl=nod[id].pr=l; nod[id].pos={l, l}; st[id].sum=st[id].pre=st[id].suf=st[id].res=-a[l]; st[id].pl=st[id].pr=l; st[id].pos={l, l}; return; } int mid=(l+r)>>1; build(id<<1, l, mid); build(id<<1|1, mid+1, r); nod[id]=nod[id<<1]+nod[id<<1|1]; st[id]=st[id<<1]+st[id<<1|1]; } void apply(int id) { la[id]^=1; swap(st[id], nod[id]); } void down(int id) { if(!la[id]) return; apply(id<<1); apply(id<<1|1); la[id]=0; } void update(int id, int l, int r, int u, int v) { if(l>v || r<u) return; if(l>=u && r<=v) return void(apply(id)); int mid=(l+r)>>1; down(id); update(id<<1, l, mid, u, v); update(id<<1|1, mid+1, r, u, v); nod[id]=nod[id<<1]+nod[id<<1|1]; st[id]=st[id<<1]+st[id<<1|1]; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>k; for(int i = 1; i <= n; i++) cin>>a[i]; build(1, 1, n); ll ans=0, cur=0; for(int te = 0; te < k; te++) { cur+=nod[1].res; ans=max(ans, cur); ii p=nod[1].pos; update(1, 1, n, p.fi, p.se); } cout<<ans; }