// y5rbeet el dp
#include <bits/stdc++.h>
#define ll long long
#define int ll
#define ld long double
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define vi vector<int>
#define vvi vector<vi>
#define vvv vector<vvi>
#define vpi vector<pair<int,int>>
#define sz(v) (int)v.size()
#define pb push_back
#define ii pair<int,int>
#define F first
#define S second
using namespace std;
const int mod = 1e9+7, N = 1e5 + 3, M = 1005;
const ll inf = 1e17;
int dx[] = {0, 0, 1, -1, 1, 1, -1, -1};
int dy[] = {-1, 1, 0, 0, 1, -1, 1, -1};
void here_we_go_again() {
int n,k;
cin>>n>>k;
vi a(n+1);
for(int i=1;i<=n;++i) cin>>a[i];
auto add=[&](ii a,ii b){
return make_pair(a.F+b.F,a.S+b.S);
};
vector<vector<ii>>dp(n+1,vector<ii>(2));
auto calc=[&](int lmb){
dp[0][0]={0,0},dp[0][1]={-inf,0};
for (int i = 1; i <= n ; ++i) {
dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
dp[i][1]=max(add(dp[i-1][0],{a[i]-lmb,1}),add(dp[i-1][1],{a[i],0}));
}
return max(dp[n][0],dp[n][1]);
};
ll l=0,r=inf,m,ans=-1;
while (l<=r){
m=(l+r)/2;
auto [val,seg]=calc(m);
if(seg>k) l=m+1;
else{
r=m-1;
ans=val+m*k;
}
}
cout<<ans;
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int tc = 1;
// cin >> tc;
for (int i = 1; i <= tc; ++i) {
// cout<<"Case #"<<i<<": ";
here_we_go_again();
}
return 0;
}
