#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
template<class T>
int chmax(T &x, T y) { return x < y ? x = y, 1 : 0; }
template<class T>
T operator+(T a, T b) {
return {a.first + b.first, a.second + b.second};
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, k; cin >> n >> k;
vector<ll> a(n);
for (ll &x : a) cin >> x;
auto check = [&] (ll x) {
vector<array<pair<ll, int>, 2>> dp(n + 1, {{{-INF, 0}, {-INF, 0}}});
dp[0][0] = {0, 0};
for (int i = 0; i < n; i++) {
chmax(dp[i][0], dp[i][1]);
chmax(dp[i][1], dp[i][0] + make_pair(-x, 1));
chmax(dp[i + 1][0], dp[i][0]);
chmax(dp[i + 1][1], dp[i][1] + make_pair(a[i], 0));
}
return max(dp[n][0], dp[n][1]);
};
ll lo = 0, hi = 3e14 + 5;
while (hi - lo > 1) {
ll m = (lo + hi) / 2;
if (check(m).second >= k) lo = m;
else hi = m;
}
auto [cost, taken] = check(lo);
cout << (cost + k * lo) << '\n';
}
