#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int MAXN=3*1e5;
int a[MAXN+1];
pair<int,int> cmp(pair<int,int> a,pair<int,int> b){
if(a.first!=b.first){
if(a.first>b.first){
return a;
}
return b;
}
if(a.second<b.second){
return a;
}
return b;
}
pair<int,int> solve(int pen,int n){
pair<int,int> DP[n+1][2];
for(int i=0;i<=n;i++){
for(int j=0;j<2;j++){
DP[i][j]={-1,-1};
}
}
DP[1][0]={0,0};
DP[1][1]={-pen+a[1],1};
for(int i=1;i<n;i++){
DP[i+1][0]=cmp(DP[i][0],DP[i][1]);
DP[i+1][1]=cmp({DP[i][0].first+a[i+1]-pen,DP[i][0].second+1},{DP[i][1].first+a[i+1],DP[i][1].second});
}
return cmp(DP[n][0],DP[n][1]);
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,k;
cin >> n >> k;
for(int i=1;i<=n;i++){
cin >> a[i];
}
pair<int,int> x=solve(0,n);
if(x.second<=k){
cout << x.first;
return 0;
}
x=solve(1,n);
int low=1,high=1e15;
low--,high++;
while(high-low>1){
int mid=((high-low)>>1)+low;
x=solve(mid,n);
if(x.second<=k){
high=mid;
}
else{
low=mid;
}
}
x=solve(high,n);
cout << x.first+k*high;
}
