#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define ll long long
const int nmax = 1e5 + 5;
const ll oo = 1e18, base = 311;
const int lg = 19, M = 105;
const ll mod = 1e9 + 7;
#define pii pair<ll, int>
#define fi first
#define se second
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' ';
using namespace std;
int n, k, f[nmax][M], a[nmax];
void ckmax(int &a, int b){
a = max(a, b);
}
deque<int> de;
multiset<pii> mt[M];
int L[nmax];
main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("code.inp", "r", stdin);
// freopen("code.ans", "w", stdout);
cin >> n >> k;
memset(f, 0x3f, sizeof f);
for(int i = 1; i <= n; ++i){
cin >> a[i];
if(i == 1) f[1][1] = a[i];
else f[i][1] = max(f[i - 1][1], a[i]);
}
for(int i = 1; i <= n; ++i){
L[i] = i - 1;
while(L[i] > 0 && a[L[i]] <= a[i]) L[i] = L[L[i]];
}
for(int i = 2; i <= n; ++i){
L[i] = max(L[i], 1);
while(de.size() && a[de.back()] <= a[i]){
int u = de.back();
for(int j = 2; j <= min(k, i); ++j){
mt[j].erase({f[L[u]][j - 1] + a[u], u});
}
de.pop_back();
}
de.push_back(i);
// for(auto p : de) cout << p << ' ';
// cout << "\n";
for(int j = 2; j <= min(k, i); ++j){
mt[j].insert({f[L[i]][j - 1] + a[i], i});
auto it = *mt[j].begin();
f[i][j] = it.fi;
}
}
cout << f[n][k];
}
/*
5 3 2
2 3 3
3 5 5
5 1 6
5 4 3
*/
