#include <bits/stdc++.h>
#define ALL(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
/*ll n,k;
vector<ll> nums;
pair<ll,ll> solve(ll penal){
pair<ll,ll> dp[n][2];
dp[0][0]={0,0};
dp[0][1]={nums[0]-penal,1};
for(ll i=1;i<n;i++){
dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
pair<ll,ll> op1={dp[i-1][0].first+nums[i]-penal,dp[i-1][0].second+1};
pair<ll,ll> op2={dp[i-1][1].first+nums[i],dp[i-1][1].second};
dp[i][1]=max(op1,op2);
}
return max(dp[n-1][0],dp[n-1][1]);
}
ll main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin >> n >> k;
nums.resize(n);
for(ll i=0;i<n;i++){
cin >> nums[i];
}
ll l=0,r=1e18;
while(l<r){
ll mid=(l+r+1)>>1;
// mayor mid=menor k
if(solve(mid).second>=k){
l=mid;
}else{
r=mid-1;
}
}
pair<ll,ll> res=solve(l);
cout << res.first+k*l;
}*/
// sol 2
bool xd;
ll n,k,a,de[300002],iz[300002];
ll findne(ll x){return (x==de[x])?x:de[x]=findne(de[x]);}
ll findan(ll x){return (x==iz[x])?x:iz[x]=findan(iz[x]);}
struct link{
ll val;
link* left;
link* right;
};
ll res=0;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin >> n >> k;
vector<ll> nums;
for(ll i=0;i<n;i++){
cin >> a;
if(a>0)xd=true;
if(!xd && a<=0)continue;
if(!nums.empty() && a*nums.back()>0)nums.back()+=a;
else nums.push_back(a);
}
while(!nums.empty() && nums.back()<=0)nums.pop_back();
ll can=(nums.size()+1)/2;
reverse(ALL(nums));
nums.push_back(0);
reverse(ALL(nums));
nums.push_back(0);
//for(auto u:nums)cout << u << ' ';
cout << endl;
priority_queue<pair<pair<ll,bool>,ll>,vector<pair<pair<ll,bool>,ll>>,greater<pair<pair<ll,bool>,ll>>> orden;
for(ll i=1;i<nums.size()-1;i++){
orden.push({{abs(nums[i]),(nums[i]>=0)},i});
}
for(ll i=0;i<nums.size();i++){
de[i]=iz[i]=i;
}
while(can>k){
ll top=orden.top().second;
orden.pop();
// unir con al lado
//cout << "a";
if(findne(top)!=top)continue;
ll sig=findne(top+1),ante=findan(top-1);
if(sig!=nums.size()-1 && ante!=0){can--;}
else if(nums[top]>0){can--;}
//cout << can << ' ' << top << ' ' << ante << ' ' << sig << '\n';
//break;
if(sig!=nums.size()-1){
//unir;
nums[top]+=nums[sig];
de[sig]=sig+1;
iz[sig]=sig-1;
}
if(ante!=0){
nums[top]+=nums[ante];
de[ante]=ante+1;
iz[ante]=ante-1;
}
orden.push({{abs(nums[top]),(nums[top]>=0)},top});
/*for(ll i=1;i<nums.size()-1;i++){
if(findne(i)==i)cout << nums[i] << ' ';
}
cout << '\n';*/
//break;
// 1 2 3 4 5
// 1 -2 3 -1 5
// -1 3 -1 5
//
}
for(ll i=1;i<nums.size()-1;i++){
if(findne(i)==i && nums[i]>0)res+=nums[i];
}
cout << res;
}
