#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, int> pli; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<vector<int>> vvi; #define pb push_back #define eb emplace_back #define ppb pop_back #define ppf pop_front #define pf push_front #define bk back() #define frnt front() #define ins insert #define er erase #define sc second #define fr first #define mp make_pair #define mt make_tuple #define lb lower_bound #define ub upper_bound #define REP(i,n) for (int i = 0; i < n; ++i) #define REP1(i,n) for (int i = 1; i <= n; ++i) #define REPV(i,n) for (int i = n-1; i >= 0; --i) #define REPV1(i, n) for (int i = n; i > 0; --i) #define ALL(a) a.begin(), a.end() #define SORT(a) sort(ALL(a)) #define MNTO(x,y) x = min(x, (__typeof__(x))y) #define MXTO(x,y) x = max(x, (__typeof__(x))y) pli solve(const vll &a, ll l) { int n = a.size(); vll s(n+1, 0); REP(i, n) s[i+1] = s[i]+a[i]; ll pv = 0, bpv = 0; int pc = 0, bpc = 0; REP1(i, n) { ll vs = pv; int cs = pc; ll vt = bpv+s[i]-l; int ct = bpc+1; ll cv; int cc; if (vt > vs || (vt == vs && ct > cs)) { cv = vt; cc = ct; } else { cv = vs; cc = cs; } ll cp = cv -s[i]; if (cp > bpv || (cp == bpv && cc > bpc)) { bpv = cp; bpc = cc; } pv = cv; pc = cc; } return {pv, pc}; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, k; cin >> n >> k; vll a(n); REP(i, n) cin >> a[i]; auto base = solve(a, 0); if (base.sc <= k) { cout << base.fr; return 0; } ll lo = 1, hi = 1e14; while (lo <= hi) { ll mid = (lo+hi) >> 1; auto res = solve(a, mid); if (res.sc > k) { lo = mid+1; } else { hi = mid-1; } } auto finaldp = solve(a, lo); ll dpval = finaldp.fr; int t = finaldp.sc; ll ans = dpval + lo*t; cout << ans; return 0; }