#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double
const int MAXN = 1e6;
const ll INF = 4e18;
const int MOD = 998244353;
struct ST{
ll n;
vector<ll> sg;
ST(ll _n){
n = _n;
sg.resize(4 * n + 5);
}
void upd(ll l, ll r, ll cur, ll idx, ll val){
if(l == r) sg[cur] = val;
else{
ll mid = (l + r) / 2;
if(idx <= mid) upd(l, mid, cur * 2, idx, val);
else upd(mid + 1, r, cur * 2 + 1, idx, val);
sg[cur] = min(sg[cur * 2], sg[cur * 2 + 1]);
}
}
ll query(ll l, ll r, ll cur, ll x, ll y){
if(l > y || r < x) return INF;
if(l >= x && r <= y) return sg[cur];
ll mid = (l + r) / 2;
return min(query(l, mid, cur * 2, x, y), query(mid + 1, r, cur * 2 + 1, x, y));
}
};
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tc = 1;
// cin >> tc;
for(;tc--;){
ll N, K; cin >> N >> K;
vector<ll> a(N + 5), lf(N + 5, 1), rg(N + 5, N);
for(int i = 1; i <= N; i++) cin >> a[i];
stack<ll> stk;
for(int i = 1; i <= N; i++){
while(!stk.empty() && a[stk.top()] <= a[i]) stk.pop();
if(!stk.empty()) lf[i] = stk.top() + 1;
stk.push(i);
}
while(!stk.empty()) stk.pop();
for(int i = N; i >= 1; --i){
while(!stk.empty() && a[stk.top()] <= a[i]) stk.pop();
if(!stk.empty()) rg[i] = stk.top() - 1;
stk.push(i);
}
vector<ll> dp(N + 5, INF);
dp[0] = 0;
ST sg(N + 1);
for(int i = 0; i <= N; i++) sg.upd(0, N, 1, i, dp[i]);
for(int i = 1; i <= K; i++){
vector<ll> ndp(N + 5, INF);
priority_queue<pii, vector<pii>, greater<pii>> pq;
for(int j = 1; j <= N; j++){
ll val = sg.query(0, N, 1, lf[j] - 1, j - 1);
pq.push({val + a[j], rg[j]});
while(pq.top().sec < j) pq.pop();
ndp[j] = pq.top().fi;
}
for(int j = 0; j <= N; j++) sg.upd(0, N, 1, j, ndp[j]);
dp.swap(ndp);
}
cout << dp[N] << "\n";
}
}
/*
1 2 3 4 5 6 7
*/
