#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,O3")
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size()
const int INF = 1e18;
inline void solve(){
int n, k;
cin >> n >> k;
vi a(n);
for(int i = 0; i < n; i++){
cin >> a[i];
}
auto penalty_solve = [&](int penalty) -> pii {
vector<vector<pii>> dp(n, vector<pii>(2)); // dp[index][open/close]
dp[0][0] = {0, 0}, dp[0][1] = {a[0] - penalty, 1};
for(int i = 1; i < n; i++){ // open and close interval
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = max(pii{dp[i - 1][0].fi + a[i] - penalty, dp[i - 1][0].se + 1}, pii{dp[i - 1][1].fi + a[i], dp[i - 1][1].se});
}
return max(dp[n - 1][0], dp[n - 1][1]);
};
auto wqs = [&]() -> int {
int lo = 0, hi = INF, mid, ret = lo;
while(hi >= lo){
mid = (lo + hi + 1) >> 1;
pii res = penalty_solve(mid);
if(res.se >= k){
ret = mid;
lo = mid + 1;
}
else{
hi = mid - 1;
}
}
return penalty_solve(ret).fi + ret * k;
};
cout << wqs() << "\n";
return;
}
signed main(){
ios_base::sync_with_stdio(false); cin.tie(0);
int t = 1;
//cin >> t;
while(t--){
solve();
}
return 0;
}
