#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pp;
#define all(a) (a).begin(), (a).end()
#define what_is(x) cerr << #x << " is " << x << '\n';
#define print(a) for (const auto &x : (a)) cout << x << ' '; cout << '\n';
const int N = 2e5 + 7;
const int MOD = 1e9 + 7;
const int INF = 1e15;
void solve() {
int n, k; cin >> n >> k;
vector<int> a(n + 1);
vector<int> pre(n + 1);
for (int i = 1; i <= n; ++i) {
cin >> a[i];
pre[i] = pre[i - 1] + a[i];
}
// The maximum sum when taking 3 segments and some segments may be big
// we will add some random value into the
auto check = [&](int val)->pp {
vector<int> dp(n + 1), g(n + 1);
int mxDp = 0, mxG = 0;
for (int i = 1; i <= n; ++i) {
int sum = pre[i] + mxDp - val;
dp[i] = dp[i - 1];
g[i] = g[i - 1];
if (sum > dp[i]) {
dp[i] = sum;
g[i] = mxG + 1;
}
// *** Fix: compare to dp[i] - pre[i], not pre[i-1] ***
if (dp[i] - pre[i] > mxDp) {
mxDp = dp[i] - pre[i];
mxG = g[i];
} else if (dp[i] - pre[i] == mxDp) {
mxG = min(mxG, g[i]);
}
}
return {dp[n], g[n]};
};
int l = 0, r = 1e18, pos = -1;
int res = 0;
while (l <= r) {
int mid = (l + r) / 2;
auto [ans, count] = check(mid);
// cout << ans << ' ' << count << '\n';
if (count <= k) {
res = max(res, ans + mid * count);
r = mid - 1;
} else {
l = mid + 1;
}
}
cout << res << endl;
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// #ifndef ONLINE_JUDGE
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// #endif
int tt = 1;
// cin >> tt;
while (tt--) {
solve();
}
return 0;
}
