#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const __int128 INF = (__int128)4e18;
int N, K;
vector<ll> A;
// returns {best_value_with_penalties, segment_count}
pair<__int128,int> solve(__int128 m){
__int128 dp0 = 0, dp1 = -INF;
int c0 = 0, c1 = 0;
for(int i = 0; i < N; i++){
__int128 x = A[i];
__int128 t1 = dp1 + x;
int tc1 = c1;
__int128 t2 = dp0 + x - m;
int tc2 = c0 + 1;
__int128 ndp1; int nc1;
if(t1 >= t2){ ndp1 = t1; nc1 = tc1; }
else { ndp1 = t2; nc1 = tc2; }
__int128 ndp0; int nc0;
if(dp0 >= dp1){ ndp0 = dp0; nc0 = c0; }
else { ndp0 = dp1; nc0 = c1; }
dp1 = ndp1; c1 = nc1;
dp0 = ndp0; c0 = nc0;
}
if(dp0 >= dp1) return {dp0, c0};
else return {dp1, c1};
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> K;
A.resize(N);
for(int i = 0; i < N; i++) cin >> A[i];
__int128 lo = -(__int128)1e15, hi = (__int128)1e15, best = hi;
while(lo <= hi){
__int128 mid = (lo + hi) >> 1;
auto [val, cnt] = solve(mid);
if(cnt <= K){
best = mid;
hi = mid - 1;
} else {
lo = mid + 1;
}
}
auto [val, cnt] = solve(best);
__int128 ans = val + best * K;
cout << (ll)ans << "\n";
return 0;
}
