#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 6;
const ll INF = 1e15;
ll Old[N], New[N];
int a[N], sz;
pair<ll,ll> p[N];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n, k;
cin >> n >> k;
for (int i = 1 ; i <= n ; ++ i) {
cin >> a[i];
Old[i] = max(Old[i - 1], (ll)a[i]);
}
for (int j = 2 ; j <= k ; ++ j) {
sz = 0;
for (int i = 1 ; i <= n ; ++ i) {
ll Mn = j <= i ? Old[i - 1] : INF;
while (sz && p[sz - 1].first <= a[i]) Mn = min(Mn, p[sz - 1].second), sz--;
if (!sz || a[i] + Mn < p[sz - 1].first + p[sz - 1].second) sz++, p[sz - 1] = {a[i], Mn};
New[i] = p[sz - 1].first + p[sz - 1].second;
}
swap(Old, New);
}
cout << Old[n];
}
