#include <bits/stdc++.h>
#define ll int64_t
#define ld long double
using namespace std;
//
const int maxn =3e5+5;
const int mod = 1e9+7; // 998244353,1610612741
const ll inf = 1e18;
const ld pi = atan(1.0L)*4;
int n,k,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;
int m=n;
vector<int> a={-1};
for (int i=1;i<=n;i++) {
int x;
cin >>x;
if (x) a.push_back(x);
}
n=a.size()-1;
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<=m;i++) res[i]=sum;
for (int i=cnt-1;i>=1;i--) {
while (cur>i) {
while (1) {
auto p=q.top();
q.pop();
it =s.lower_bound({p.second,-mod});
if ((*it).first==p.second) break;
}
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);
if (nw){
s.insert({id,nw});
q.push({abs(nw),id});
}
}
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);
if (nw){
s.insert({id,nw});
q.push({abs(nw),id});
}
}
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);
if (nw){
s.insert({id,nw});
q.push({abs(nw),id});
}
}
}
res[i]=sum;
}
cout<<res[k]<<'\n';
}
return 0;
}
