#include <bits/stdc++.h>
#define fastio cin.tie(0)->ios::sync_with_stdio(0);
using namespace std;
typedef long long ll;
ll N,K;
vector<ll> A;
pair<ll,ll> f(ll m){
vector<ll> dp1(N, 0), dp2(N, 0), cnt1(N, 0), cnt2(N, 0);
dp2[0] = A[0] - m; cnt2[0] = 1;
for(ll i=1;i<N;i++){
if(dp1[i-1] > dp2[i-1] || (dp1[i-1] == dp2[i-1] && cnt1[i-1] > cnt2[i-1])) dp1[i] = dp1[i-1], cnt1[i] = cnt1[i-1];
else dp1[i] = dp2[i-1], cnt1[i] = cnt2[i-1];
if(dp1[i-1] - m > dp2[i-1] || (dp1[i-1] - m == dp2[i-1] && cnt1[i-1] + 1 > cnt2[i-1])) dp2[i] = dp1[i-1] - m + A[i], cnt2[i] = cnt1[i-1] + 1;
else dp2[i] = dp2[i-1] + A[i], cnt2[i] = cnt2[i-1];
}
if(dp1[N-1] > dp2[N-1] || (dp1[N-1] == dp2[N-1] && cnt1[N-1] > cnt2[N-1])) return {dp1[N-1], cnt1[N-1]};
return {dp2[N-1], cnt2[N-1]};
}
int main(){
fastio;
ll l=0,r=0;
cin >> N >> K;
A.resize(N);
for(auto &a : A) cin >> a, r+=(a>0)?a:0;
ll mopt;
while(l <= r){
ll m = (l + r)/2;
auto [v, c] = f(m);
if(c <= K){
r = m - 1;
mopt = m;
} else l = m + 1;
}
auto [v, c] = f(mopt);
cout << v + c*mopt;
}
