#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18+7;
inline void clear(vector<ll>&v)
{
v.clear();
v.shrink_to_fit();
return;
}
inline void merge(vector<ll>&rt,vector<ll>&l,vector<ll>&r)
{
rt.clear();
rt.reserve((int)l.size()+(int)r.size()-1);
rt.eb(l[0]+r[0]);
register int li=1,ri=1;
while(li<(int)l.size()&&ri<(int)r.size())
{
if(l[li]-l[li-1]>r[ri]-r[ri-1])
rt.eb(rt.back()+l[li]-l[li-1]),li++;
else
rt.eb(rt.back()+r[ri]-r[ri-1]),ri++;
}
while(li<(int)l.size())
rt.eb(rt.back()+l[li]-l[li-1]),li++;
while(ri<(int)r.size())
rt.eb(rt.back()+r[ri]-r[ri-1]),ri++;
return;
}
inline void mx(vector<ll>&rt,vector<ll>&r)
{
if(rt.size()<r.size())
rt.resize(r.size(),-INF);
for(register int i=0;i<(int)r.size();i++)
rt[i]=max(rt[i],r[i]);
return;
}
vector<ll>no[1200010],l[1200010],r[1200010],lr[1200010];
void dnc(int n,int s,int e,vector<ll>&v)
{
if(s==e)
{
no[n].eb(0);
no[n].eb(v[s]);
l[n].eb(v[s]);
r[n].eb(v[s]);
lr[n].eb(v[s]);
return;
}
int m=s+(e-s)/2;
dnc(n*2,s,m,v);
dnc(n*2+1,m+1,e,v);
vector<ll>v1,v2,v3,v4;
merge(no[n],no[n*2],no[n*2+1]);
merge(l[n],lr[n*2],l[n*2+1]);
merge(r[n],r[n*2],lr[n*2+1]);
merge(lr[n],lr[n*2],lr[n*2+1]);
merge(v1,r[n*2],l[n*2+1]);
merge(v2,l[n*2],no[n*2+1]);
merge(v3,no[n*2],r[n*2+1]);
merge(v4,l[n*2],r[n*2+1]);
v1.insert(v1.begin(),-INF);
v4.insert(v4.begin(),-INF);
mx(no[n],v1);
mx(l[n],v2);
mx(r[n],v3);
mx(lr[n],v4);
for(int i=n*2;i<n*2+2;i++)
clear(no[i]),clear(l[i]),clear(r[i]),clear(lr[i]);
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n,k;
cin>>n>>k;
vector<ll>v(n);
for(ll&t:v)
cin>>t;
if(k==1)
{
ll ans=0;
ll ca=0;
for(ll&t:v)
ans=max(ans,ca=max(ca+t,0ll));
cout<<ans<<endl;
return 0;
}
bool allp=1;
for(ll&t:v)
if(t<0)
allp=0;
if(allp)
{
ll ans=0;
for(ll&t:v)
ans+=t;
cout<<ans<<endl;
return 0;
}
v.insert(v.begin(),0ll);
dnc(1,1,n,v);
ll ans=0;
for(register int i=0;i<=k;i++)
ans=max(ans,no[1][i]);
cout<<ans<<'\n';
return 0;
}
