#include <bits/stdc++.h> using namespace std; using ll = long long; const ll NEG = (ll)-9e18; struct Node { ll val; // value = sum - lambda * segments int cnt; // number of segments used Node(ll v = NEG, int c = 0) : val(v), cnt(c) {} }; inline Node better(const Node &a, const Node &b){ if (a.val != b.val) return (a.val > b.val) ? a : b; // tie-break: prefer fewer segments return (a.cnt < b.cnt) ? a : b; } pair<ll,int> solve_with_lambda(const vector<ll> &A, ll lambda){ int n = (int)A.size(); Node dp(0,0); // best for prefix processed so far Node best_end(NEG,0); // best value for a solution that ends at current i for (int i = 0; i < n; ++i){ // option 1: extend previous ending segment Node extend = Node(best_end.val + A[i], best_end.cnt); // option 2: start new segment at i (pay -lambda) Node start_new = Node(dp.val + A[i] - lambda, dp.cnt + 1); best_end = better(extend, start_new); dp = better(dp, best_end); } return {dp.val, dp.cnt}; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N, K; if (!(cin >> N >> K)) return 0; vector<ll> A(N); for (int i = 0; i < N; ++i) cin >> A[i]; // Binary search lambda: find largest lambda such that cnt >= K ll lo = - (ll)1e15, hi = (ll)1e15; while (lo < hi) { ll mid = lo + ((hi - lo + 1) >> 1); auto [val, cnt] = solve_with_lambda(A, mid); if (cnt >= K) lo = mid; else hi = mid - 1; } ll lambda = lo; auto [val, cnt] = solve_with_lambda(A, lambda); // answer for at most K segments: ll answer = val + lambda * (ll)K; cout << answer << '\n'; return 0; }