#include <bits/stdc++.h>
#define F first
#define S second
#define rep(i, a, b) for(int i = (a); i < (b); ++i)
#define per(i, a, b) for(int i = (b)-1; i >= (a); --i)
#define bck(i, a, b) if ((i) >= (a) && (i) < (b))
#define trav(x, a) for (auto &x : (a))
#define sz(a) (int)(a).size()
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define dbg(X) std::cerr << "[DBG]("<<__FUNCTION__<<":"<<__LINE__<<") " << #X << ": " << X << std::endl;
using namespace std;
typedef long long ll;
typedef string str;
template<typename T> using vec = vector<T>;
template<typename T> using pq = priority_queue<T, vector<T>, std::greater<T>>;
template<typename T> using mxpq = priority_queue<T>;
typedef pair<int,int> pii;
typedef vec<int> vi;
typedef vec<pii> vii;
typedef vec<vi> vvi;
typedef pair<ll,ll> pll;
typedef vec<ll> vl;
typedef vec<pll> vll;
typedef vec<vl> vvl;
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template<typename A, typename B>
istream& operator>>(istream& s, pair<A,B>& p) { return s>>p.first>>p.second; }
template<typename A, typename B>
ostream& operator<<(ostream& s, const pair<A,B>& p) { return s<<"{"<<p.first<<", "<<p.second<<"}"; }
template<typename T>
istream& operator>>(istream& s, vec<T>& p) { for (T& t : p) s >> t; return s; }
template<typename T>
ostream& operator<<(ostream& s, const vec<T>& p) { for (const T& t : p) s << t << " "; return s; }
pll go(vl& a, ll cost) {
int n = sz(a);
vl dp0(n),dp1(n), cnt1(n), cnt0(n);
dp0[0] = 0;
dp1[0] = a[0] - cost;
cnt0[0]=0;
cnt1[0]=1;
rep(i, 1, n) {
dp0[i] = max(dp0[i-1], dp1[i-1]);
if (dp0[i-1] >= dp1[i-1]) cnt0[i] = cnt0[i-1];
else cnt0[i] = cnt1[i-1];
dp1[i] = max(dp0[i-1] - cost, dp1[i-1]) + a[i];
if (dp0[i-1] - cost > dp1[i-1]) {
cnt1[i] = cnt0[i-1] + 1;
} else {
cnt1[i] = cnt1[i-1];
}
}
if (dp0.back() >= dp1.back()) {
return {dp0.back(), cnt0.back()};
} else {
return {dp1.back(), cnt1.back()};
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n, k; cin >> n >> k;
vl a(n); cin >> a;
/* cout << go(a, 0) << endl; */
/* cout << go(a, 1) << endl; */
/* cout << go(a, 2) << endl; */
/* cout << go(a, 3) << endl; */
ll lo = 0, hi = 1e12;
while (hi - lo > 1) {
ll m = (lo + hi)/2;
ll x = go(a, m).S;
if (x >= k) lo = m;
else hi=m;
}
cout << go(a, lo).F + lo*k << endl;
}
