// Template
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
void dbg_out() { cerr << endl; }
template <typename H, typename... T>
void dbg_out(H h, T... t) { cerr << ' ' << h; dbg_out(t...); }
#define dbg(...) { cerr << #__VA_ARGS__ << ':'; dbg_out(__VA_ARGS__); }
const int INF = 1e9;
int solve() {
int n, k; cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++) cin>>a[i];
// I want (at most) K segments.
// Positive values I always want to take the most.
auto eval = [&](int lambda) {
// Lambda is the penalty.
// Creating a new segment costs lambda.
// dp[i][0] := Best sum not using i.
// dp[i][1] := Best sum using i.
vector<vector<pair<int, int>>> dp(n, vector<pair<int, int>>(2, {-INF, -INF}));
dp[0][0] = {0, 0};
dp[0][1] = {a[0]-lambda, 1};
for (int i = 1; i < n; i++) {
dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
dp[i][1] = max<pair<int, int>>(
{dp[i-1][0].first + a[i] - lambda, dp[i-1][0].second + 1},
{dp[i-1][1].first + a[i], dp[i-1][1].second}
);
}
return max(dp[n-1][0], dp[n-1][1]);
};
// eval(0) will use a segment for each positive value.
// eval(INF) will never create a segment.
int lo = 0, hi = INF;
while (hi-lo > 1) {
int mid = (lo + hi)/2;
auto [cost, used] = eval(mid);
if (used > k) lo = mid;
else hi = mid;
}
auto [res, _] = eval(hi);
return res + k*hi;
}
signed main() {
cin.tie(0)->sync_with_stdio(false);
cin.exceptions(cin.failbit);
cout << solve() << '\n';
return 0;
}
