#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 = res.fi + mid * res.se; lo = mid; } else{ hi = mid - 1; } } return penalty_solve(lo).fi + lo * 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; }