#include <bits/stdc++.h>
#define ll int64_t
#define ld long double
using namespace std;
//
const int maxn =1e5+5;
const int mod = 1e9+7; // 998244353,1610612741
const ll inf = 1e18;
const ld pi = atan(1.0L)*4;
int n,k,a[maxn],res[maxn];
int main() {
// freopen("../input.inp","r",stdin);
// freopen("output.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >>n>>k;
for (int i=1;i<=n;i++) cin >>a[i];
int i=1;
set<pair<int,int>> s;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
while (i<=n) {
int val=0;
int j=i;
while (j<=n&&a[i]*a[j]>=0) val+=a[j++];
s.insert({i,val});
i=j;
}
auto it=s.begin();
while (!s.empty()&&(*it).second<0) s.erase(it),it=s.begin();
if (!s.empty()){
it =prev(s.end());
while (!s.empty()&&(*it).second<0) s.erase(it),it=prev(s.end());
}
int cnt=s.size()/2+1;
if (s.size()==0) {
for (int i=1;i<=n;i++) res[i]=0;
cout<<res[k];
}
else if (cnt==1) {
for (int i=cnt;i<=n;i++) res[i]=(*s.begin()).second;
cout<<res[k];
}
else {
for (auto i=s.begin();i!=s.end();i++) q.push({abs((*i).second),(*i).first});
int cur=cnt;
int sum=0;
for (auto i:s) {
if (i.second>0) sum+=i.second;
}
for (int i=cnt;i<=n;i++) res[i]=sum;
for (int i=cnt-1;i>=1;i--) {
it=s.begin();
while (!s.empty()&&(*it).second<0) s.erase(it),it=s.begin();
it =prev(s.end());
while (!s.empty()&&(*it).second<0) s.erase(it),it=prev(s.end());
while (cur>i) {
auto p=q.top();
q.pop();
it =s.lower_bound({p.second,-mod});
int id=(*it).first;
if (it==s.begin()) {
auto nex=next(it);
cur-=((*it).second>=0)+((*nex).second>=0);
sum-=((*it).second>=0?(*it).second:0)+
((*nex).second>=0?(*nex).second:0);
int nw=(*it).second+(*nex).second;
cur +=(nw>=0);
if (nw>=0) sum+=nw;
s.erase(it);s.erase(nex);
s.insert({id,nw});
q.push({abs((*it).second),(*it).first});
}
else if (it==prev(s.end())) {
auto pre=prev(it);
cur-=((*it).second>=0)+((*pre).second>=0);
sum-=((*it).second>=0?(*it).second:0)+
((*pre).second>=0?(*pre).second:0);
int nw=(*it).second+(*pre).second;
cur +=(nw>=0);
if (nw>=0) sum+=nw;
s.erase(it);s.erase(pre);
s.insert({id,nw});
q.push({abs((*it).second),(*it).first});
}
else{
auto pre=prev(it),nex=next(it);
cur -= ((*pre).second>=0)+((*it).second>=0)+((*nex).second>=0);
sum -= ((*pre).second>=0?(*pre).second:0)+
((*it).second>=0?(*it).second:0)+
((*nex).second>=0?(*nex).second:0);
int nw=(*pre).second+(*it).second+(*nex).second;
cur +=(nw>=0);
if (nw>=0) sum+=nw;
s.erase(pre);s.erase(it);s.erase(nex);
s.insert({id,nw});
it=s.find({id,nw});
q.push({abs((*it).second),(*it).first});
}
}
res[i]=sum;
}
cout<<res[k];
}
return 0;
}
