#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=1e5+5, maxk=105, Log=17, pot=(1<<Log);
const int inf=1e9;
struct tournament{
int t[pot*2];
void update(int x, int val){
t[x]=val;
for(x/=2; x>0; x/=2){
t[x]=max(t[x*2], t[x*2+1]);
}
}
int query(int L, int D, int x, int l, int d){
if(L>=l && D<=d){
return t[x];
}
int lijeva=0, desna=0;
if((L+D)/2>=l){
lijeva=query(L, (L+D)/2, x*2, l, d);
}
if((L+D)/2+1<=d){
desna=query((L+D)/2+1, D, x*2+1, l, d);
}
return max(lijeva, desna);
}
};
int n, k;
int dp[maxk][maxn];
int a[maxn];
tournament T;
void rijesi(int ind, int l, int d, int optl, int optd){
if(l>=d){
return;
}
int pos=(l+d)/2;
int opti, minsol=inf;
int maksi=T.query(0, pot-1, 1, min(optd, pos), pos);
for(int i=min(optd, pos)-1; i>=optl; i--){
if(minsol>maksi+dp[ind-1][i]){
minsol=maksi+dp[ind-1][i];
opti=i;
}
maksi=max(maksi, a[i]);
}
// cout << pos << ' ' << minsol << endl;
dp[ind][pos]=minsol;
rijesi(ind, l, pos, optl, opti+1);
rijesi(ind, pos+1, d, opti, optd);
}
int main(){
scanf("%d%d", &n, &k);
for(int i=0; i<n; i++){
scanf("%d", a+i+1);
T.update(i+1+pot, a[i+1]);
}
for(int i=1; i<=n; i++){
dp[0][i]=inf;
}
for(int i=1; i<=k; i++){
rijesi(i, i, n+1, i-1, n);
}
printf("%d\n", dp[k][n]);
}
