#include <bits/stdc++.h>
using namespace std;
#define int long long
using i128 = __int128_t;
int n, k;
const int NEG_INF = LLONG_MIN / 4;
vector<int> a;
inline pair<int,int> better(const pair<int,int> &A, const pair<int,int> &B) {
if (A.first != B.first) return (A.first > B.first) ? A : B;
return (A.second >= B.second) ? A : B; // tie: prefer larger count
}
// Evaluate one lambda (penalty). Returns {best_adjusted_value, segments_used}
pair<int,int> eval_lambda(int lambda) {
pair<int,int> dp0 = {0, 0}; // best up to i (maybe not ending at i)
pair<int,int> dp1 = {NEG_INF, 0}; // best with a segment that ends exactly at i
for (int i = 0; i < n; ++i) {
pair<int,int> extend = { (dp1.first == NEG_INF ? NEG_INF : dp1.first + a[i]), dp1.second };
pair<int,int> start = { dp0.first + a[i] - lambda, dp0.second + 1 };
dp1 = better(extend, start);
dp0 = better(dp0, dp1);
}
return dp0;
}
int solve_lambda() {
// Use safe, tight bounds derived from input to avoid overflow
// sumAbs = sum |a[i]| <= n * 1e9 <= 3e14 (within 64-bit safely)
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
if (eval_lambda(mid).second >= k) L = mid;
else R = mid - 1;
}
return L;
}
string toString128(i128 x) {
if (x == 0) return "0";
bool neg = x < 0;
if (neg) x = -x;
string s;
while (x > 0) {
int d = (int)(x % 10);
s.push_back(char('0' + d));
x /= 10;
}
if (neg) s.push_back('-');
reverse(s.begin(), s.end());
return s;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (!(cin >> n >> k)) return 0;
a.assign(n, 0);
for (int i = 0; i < n; ++i) cin >> a[i];
// 1) find lambda boundary
int bestLambda = solve_lambda();
// 2) evaluate a few nearby lambdas to be robust against tie/boundary issues
auto pL = eval_lambda(bestLambda);
auto pLm1 = eval_lambda(bestLambda - 1);
// also check bestLambda+1 (optional, cheap)
auto pLp1 = eval_lambda(bestLambda + 1);
// 3) from each evaluation we can build a candidate answer for exactly K segments:
// answer_candidate = adjusted_value + lambda * K
// Note: adjusted_value = best( f(x) - lambda*x ) = f(c) - lambda*c for the chosen c
// And candidate = (f(c) - lambda*c) + lambda*K = f(c) + lambda*(K - c).
// This is a valid candidate (possibly not the true maximum for exactly K),
// but checking neighbors covers boundary/tie cases.
i128 cand1 = (i128)pL.first + (i128)bestLambda * (i128)k;
i128 cand2 = (i128)pLm1.first + (i128)(bestLambda - 1) * (i128)k;
i128 cand3 = (i128)pLp1.first + (i128)(bestLambda + 1) * (i128)k;
// 4) final answer is max among candidates and 0 (empty segments allowed)
i128 ans128 = cand1;
if (cand2 > ans128) ans128 = cand2;
if (cand3 > ans128) ans128 = cand3;
if (ans128 < 0) ans128 = 0;
cout << toString128(ans128) << '\n';
return 0;
}
