#include <bits/stdc++.h> using namespace std; pair<long long,int> calc(const vector<long long>& a, long long p) { int n = a.size(); vector<long long> pref(n+1); for (int i = 0; i < n; i++) pref[i+1] = pref[i] + a[i]; long long dp = 0, best = 0; int cnt = 0, bestc = 0; for (int i = 1; i <= n; i++) { long long v1 = dp; int c1 = cnt; long long v2 = best + pref[i] - p; int c2 = bestc + 1; if (v2 > v1 || (v2 == v1 && c2 > c1)) { dp = v2; cnt = c2; } long long cur = dp - pref[i]; if (cur > best || (cur == best && cnt > bestc)) { best = cur; bestc = cnt; } } return {dp, cnt}; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin >> n >> k; vector<long long> a(n); for (auto &x : a) cin >> x; auto base = calc(a, 0); if (base.second <= k) { cout << base.first; return 0; } long long l = 1, r = 1e14; while (l <= r) { long long m = (l + r) >> 1; if (calc(a, m).second > k) l = m + 1; else r = m - 1; } auto res = calc(a, l); cout << res.first + l * res.second; }