// 2025/8/10: 911Lil_Marrikh - ECPC-2025 Medalists
#include <bits/stdc++.h>
using namespace std;
// #define int int64_t
#define ll int64_t
#define el "\n"
void work(int tc) {
int n, k; cin >> n >> k;
int a[n]; for (auto &i : a) cin >> i;
auto solve = [&] (ll lmd) {
pair<ll, int> dp[2][2];
dp[0][0] = {0, 0};
dp[0][1] = dp[1][0] = dp[1][1] = {-1e18, -1e9};
for (int i = 0; i < n; i++) {
dp[1][0] = max(dp[0][0], dp[0][1]);
dp[1][1] = max<pair<ll, int>>(
{dp[0][0].first + a[i] - lmd, dp[0][0].second + 1},
{dp[0][1].first + a[i], dp[0][1].second}
);
swap(dp[0], dp[1]);
dp[1][0] = dp[1][1] = {-1e18, -1e9};
}
return max(dp[0][0], dp[0][1]);
};
ll l = 0, r = 1e18, mid;
while (l <= r) {
mid = l + r >> 1;
if (solve(mid).second > k) {
l = mid + 1;
} else {
r = mid - 1;
}
}
cout << solve(l).first + l * k;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
// #ifndef ONLINE_JUDGE
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// #endif
int _t = 1;
// cin >> _t;
for (int i = 1; i <= _t; i++) {
work(i);
}
}
