#include <bits/stdc++.h> using namespace std; using ll = long long; const ll INF = 1e18; template<class T> int chmax(T &x, T y) { if (x < y) { x = y; return 1; } return 0; } 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]); if (chmax(dp[i][1].first, dp[i][0].first - x)) dp[i][1].second = dp[i][0].second + 1; chmax(dp[i + 1][0], dp[i][0]); if (chmax(dp[i + 1][1].first, dp[i][1].first + a[i])) dp[i + 1][1].second = dp[i][1].second; } return max(dp[n][0], dp[n][1]); }; int lo = 0, hi = 1e9 + 5; while (hi - lo > 1) { int m = (lo + hi) / 2; if (check(m).second >= k) lo = m; else hi = m; } auto [cost, taken] = check(lo); cout << cost + 1ll * k * lo << '\n'; }