#include<bits/stdc++.h>
using namespace std;
const long long maxn=300000+10;
long long n,k,all[maxn];
pair<long long ,long long>check(long long mid){
vector<pair<long long ,long long>>dp0(n),dp1(n);
pair<long long,long long>ret;
for(long long i=0;i<n;i++){
dp1[i]=make_pair(all[i]-mid,1);
dp0[i]=make_pair(0,0);
if(i==0){
continue;
}
dp1[i]=max(dp1[i],make_pair(dp0[i-1].first-mid+all[i],dp0[i-1].second+1));
dp1[i]=max(dp1[i],make_pair(dp1[i-1].first+all[i],dp1[i-1].second));
dp0[i]=max(dp0[i],dp0[i-1]);
dp0[i]=max(dp0[i],dp1[i-1]);
}
ret.second=max(dp0[n-1],dp1[n-1]).second;
for(long long i=0;i<n;i++){
dp1[i]=make_pair(all[i]-mid,-1);
dp0[i]=make_pair(0,0);
if(i==0){
continue;
}
dp1[i]=max(dp1[i],make_pair(dp0[i-1].first-mid+all[i],dp0[i-1].second-1));
dp1[i]=max(dp1[i],make_pair(dp1[i-1].first+all[i],dp1[i-1].second));
dp0[i]=max(dp0[i],dp0[i-1]);
dp0[i]=max(dp0[i],dp1[i-1]);
}
ret.first=max(dp0[n-1],dp1[n-1]).second*-1;
return ret;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>k;
for(long long i=0;i<n;i++){
cin>>all[i];
}
long long opt=0;
long long high=1e15,low=-1,mid;
while(high-low>1){
mid=(high+low)>>1;
pair<long long ,long long>stf=check(mid);
if(stf.first<=k&&stf.second>=k){
opt=mid;
break;
}
if(stf.second<k){
high=mid;
}else{
low=mid;
}
}
mid=opt;
vector<pair<long long ,long long>>dp0(n),dp1(n);
pair<long long,long long>ret;
for(long long i=0;i<n;i++){
dp1[i]=make_pair(all[i]-mid,1);
dp0[i]=make_pair(0,0);
if(i==0){
continue;
}
dp1[i]=max(dp1[i],make_pair(dp0[i-1].first-mid+all[i],dp0[i-1].second+1));
dp1[i]=max(dp1[i],make_pair(dp1[i-1].first+all[i],dp1[i-1].second));
dp0[i]=max(dp0[i],dp0[i-1]);
dp0[i]=max(dp0[i],dp1[i-1]);
}
cout<<max(dp1[n-1],dp0[n-1]).first+k*opt<<endl;
//cout<<mid<<endl;
}
