#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef tuple<int, int, int> ti;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#ifdef LOCAL
#include <debug.h>
#else
#define debug(...)
#define debugArr(...)
#endif
const int MOD = 1000000007;
const char nl = '\n';
struct Line {
mutable ll k, m, p;
bool operator<(const Line& o) const { return k < o.k; }
bool operator<(ll x) const { return p < x; }
};
void solve() {
int n, k; cin >> n >> k;
vi A(n);
rep(i, 0, n) cin >> A[i];
typedef pair<ll, ll> en;
const ll inf = 1e18;
auto calc = [&] (ll m) {
// dp[i]: max value from i..n given most recent starts at i
// I am maxing, so I want to min intervals
vector<en> dp(n + 1);
en mx = {0, 0};
for (int i = n - 1; i >= 0; i--) {
// start new interval
en cand = mx;
cand.first += max(A[i] - m, -m);
cand.second++;
dp[i] = cand;
// extends interval
cand = dp[i + 1];
if (cand.second != 0) {
cand.first += A[i];
dp[i] = max(dp[i], cand);
}
mx = max(dp[i], mx);
}
return mx;
};
// low: use all ops, high: use no ops
ll low = -1;
ll high = 1e15;
while(low + 1 < high) {
ll mid = low + (high - low)/2;
en res = calc(mid);
ll ops = res.second;
if (ops >= k) {
low = mid;
} else {
high = mid;
}
}
en res = calc(low);
cout << res.first + (ll)k * low << nl;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
int t = 1;
//cin >> t;
while(t--) solve();
}
