#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i128 = __int128_t;
struct State {
i128 val;
int cnt;
};
static inline State bestState(const State& a, const State& b) {
if (a.val != b.val) return (a.val > b.val) ? a : b;
return (a.cnt > b.cnt) ? a : b;
}
static string to_string_i128(i128 x) {
if (x == 0) return "0";
bool neg = false;
if (x < 0) { neg = true; x = -x; }
string s;
while (x > 0) {
int digit = (int)(x % 10);
s.push_back(char('0' + digit));
x /= 10;
}
if (neg) s.push_back('-');
reverse(s.begin(), s.end());
return s;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, K;
cin >> N >> K;
vector<ll> A(N);
for (int i = 0; i < N; i++) cin >> A[i];
ll posSum = 0;
for (ll x : A) if (x > 0) posSum += x;
auto solve = [&](ll lambda) -> State {
const i128 NEG = -((i128)1 << 120);
State out{0, 0};
State in{NEG, 0};
for (ll x : A) {
State extend{in.val + (i128)x, in.cnt};
State start{out.val + (i128)x - (i128)lambda, out.cnt + 1};
State in2 = bestState(extend, start);
State out2 = bestState(out, bestState(in, in2));
out = out2;
in = in2;
}
return bestState(out, in);
};
State st0 = solve(0);
if (st0.cnt <= K) {
cout << to_string_i128(st0.val) << "\n";
return 0;
}
ll lo = 0, hi = posSum + 1;
while (lo < hi) {
ll mid = lo + (hi - lo + 1) / 2;
State st = solve(mid);
if (st.cnt >= K) lo = mid;
else hi = mid - 1;
}
ll lambda = lo;
State st = solve(lambda);
i128 ans = st.val + (i128)lambda * (i128)K;
cout << to_string_i128(ans) << "\n";
return 0;
}
