#include <bits/stdc++.h> using namespace std; using ll = long long; using i128 = __int128_t; struct Node { i128 val; int cnt; Node(i128 v = (i128)-9e36, 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; return (a.cnt < b.cnt) ? a : b; // prefer fewer segments on tie } pair<i128,int> solve_with_lambda(const vector<ll> &A, i128 lambda){ int n = (int)A.size(); Node dp((i128)0, 0); // best for prefix Node best_end((i128)-9e36,0); // best that ends at current i for (int i = 0; i < n; ++i){ Node extend = Node(best_end.val + (i128)A[i], best_end.cnt); Node start_new = Node(dp.val + (i128)A[i] - lambda, dp.cnt + 1); best_end = better(extend, start_new); dp = better(dp, best_end); } return {dp.val, dp.cnt}; } // helper to print i128 string to_string_i128(i128 x){ if (x == 0) return "0"; bool neg = false; if (x < 0){ neg = true; x = -x; } string s; while (x > 0){ int digit = (int)(x % 10); s.push_back('0' + digit); x /= 10; } if (neg) s.push_back('-'); reverse(s.begin(), s.end()); return s; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N; long long K; if (!(cin >> N >> K)) return 0; vector<ll> A(N); for (int i = 0; i < N; ++i) cin >> A[i]; // set safe search bounds (i128) // choose bounds based on absolute sum to reduce useless extremes i128 sumAbs = 0; for (ll x : A) sumAbs += (i128) llabs(x); i128 lo = -sumAbs - 1; // a bit more margin i128 hi = sumAbs + 1; // binary search largest lambda such that cnt >= K while (lo < hi) { i128 mid = lo + (hi - lo + 1) / 2; auto [val, cnt] = solve_with_lambda(A, mid); if (cnt >= (int)K) lo = mid; else hi = mid - 1; } i128 lambda = lo; auto [val, cnt] = solve_with_lambda(A, lambda); i128 answer = val + lambda * (i128)K; // safe in i128 cout << to_string_i128(answer) << '\n'; return 0; }