#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, k;
const int NEG_INF = LLONG_MIN / 4; // very negative sentinel
vector<int> a;
// choose better by value; on tie prefer larger count
pair<int,int> better(const pair<int,int> &opt1, const pair<int,int> &opt2) {
if (opt1.first != opt2.first) return (opt1.first > opt2.first) ? opt1 : opt2;
return (opt1.second >= opt2.second) ? opt1 : opt2;
}
// evaluate lambda: returns {best_adjusted_value, segments_used}
pair<int,int> check(int lambda) {
pair<int,int> dp1 = {NEG_INF, 0}; // best with a segment ending at i
pair<int,int> dp0 = {0, 0}; // best up to i (not necessarily ending at i)
for (int i = 0; i < n; ++i) {
pair<int,int> opt1 = { (dp1.first == NEG_INF ? NEG_INF : dp1.first + a[i]), dp1.second }; // extend
pair<int,int> opt2 = { dp0.first + a[i] - lambda, dp0.second + 1 }; // start new
dp1 = better(opt1, opt2);
dp0 = better(dp0, dp1); // best up to i: either previous best or a segment ending at i
}
return dp0;
}
int solve() {
// safe lambda bounds computed from input sums instead of LLONG extremes
// sumAbs <= n * 1e9 <= 3e14 for constraints; we add some slack
long long sumAbs = 0;
for (int i = 0; i < n; ++i) sumAbs += llabs(a[i]);
int L = (int)(-sumAbs - 5);
int R = (int)( sumAbs + 5);
while (L < R) {
int mid = L + ((R - L + 1) >> 1); // upper mid (safe)
if (check(mid).second >= k) L = mid;
else R = mid - 1;
}
return L;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (!(cin >> n >> k)) return 0;
a.resize(n);
for (int i = 0; i < n; ++i) cin >> a[i];
int bestLambda = solve();
auto finalPr = check(bestLambda);
// Recompose final answer: adjusted_value + lambda * K (use i128 to avoid overflow)
__int128 res128 = (__int128)finalPr.first + (__int128)bestLambda * (__int128)k;
long long result = (long long)res128;
// Empty segments are allowed => answer >= 0
result = max(0LL, result);
cout << result << '\n';
return 0;
}
