#include <bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
#define pb push_back
#define ld long double
#define pll pair<int, int>
#define MAXN 100002
#define mp make_pair
/*
aliens trick / parameter search
let f(x) be the maximum with x segments.
f(x) is convex.
let l be a fixed value.
define g(x) = f(x) - l*x, thus f(x) = g(x) + l*x
let the maximum value of g(x) across all x be v(l)
and v(l) occurs at the rightmost index c(l) [it forms a range]
c is just the largest index such that f(x) - f(x-1) >= l.
thus f(c(l))-f(c(l)-1)=l
now we want to know f(k)-f(k-1)
binary search for the largest l such that c(l) >= k
f(k)-f(k-1)=largest l.
then since we defined f(k)=g(k)+l*k and we know g(k)=g(c(l))=v(l)
thus f(k)=v(l)+l*k
*/
int n,k,l;
pll mem[300005][2];
bool vis[300005][2];
vector<int> a;
pll dp(int i, bool last){
if(vis[i][last])return mem[i][last];
if(i>=n)return {0,0};
vis[i][last]=true;
pll take=dp(i+1,1), dont=dp(i+1,0);
mem[i][last]=max(
mp(take.f+a[i]-(last?0:l),take.s+(last?0:1)),
dont
);
return mem[i][last];
}
signed main(){
cin>>n>>k;
int pos=0,val=0;
for(int i=0;i<n;i++){
int cur;
cin>>cur;
if(cur==0)continue;
if(a.empty()){
a.push_back(cur);
continue;
}
if((cur>0 and a.back()>0) or (cur<0 and a.back()<0)){
a.back()+=cur;
}
else{
a.push_back(cur);
}
}
n=a.size();
for(int i=0;i<n;i++){
if(a[i]>0){
pos++;
val+=a[i];
}
}
int hi=1e15, lo=1;
if(pos<=k){
cout<<val;
return 0;
}
pll vc;
int ansv,ansl;
while(lo<=hi){
for(int i=0;i<n;i++) {
vis[i][0]=vis[i][1]=0;
}
l=(lo+hi)/2;
vc=dp(0,0);
//~ printf("current lambda %lld, highest value %lld, max seg %lld\n",l,vc.f,vc.s);
if(vc.s>=k){
ansv=vc.f;
ansl=l;
lo=l+1;
}
else{
hi=l-1;
}
}
cout<<ansv+ansl*k;
}
