#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const ll INF = 1e18;
void testcase() {
int n, k;
cin >> n >> k;
vector<ll> a(n), pref(n + 1);
for (int i = 0; i < n; ++i) {
cin >> a[i];
pref[i + 1] = pref[i] + a[i];
}
auto check = [&](ll f) {
vector<pair<ll, ll>> dp(n + 1, {-INF, INF});
dp[0] = {0, 0};
pair<ll, ll> lst = {0, 0}, val = {0, 0}, mx = {0, 0};
for (int i = 0; i < n; ++i) {
lst = max(lst, dp[i]);
val = max(val, {lst.first - pref[i + 1], lst.second + 1});
val = max(val, {lst.first - pref[i], lst.second + 1});
dp[i + 1] = {val.first + pref[i + 1] - f, val.second};
mx = max(mx, dp[i + 1]);
}
return mx;
};
ll l = -1e12, r = 1e12, ans = 0;
while (l <= r) {
ll mid = (l + r) / 2;
auto [val, kk] = check(mid);
if (kk >= k) {
l = mid + 1;
ans = val + 1ll * k * mid;
} else {
r = mid - 1;
}
}
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tt = 1;
// cin >> tt;
while (tt--) {
testcase();
}
return 0;
}
