#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;
}
