#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define inp(data_name) freopen(data_name,"r",stdin);
#define out(data_name) freopen(data_name,"w",stdout);
#define name "main"
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define FORD(i,a,b) for(int i=(b);i>=(a);--i)
#define N 1'000'00
#define MAXK 1'00
const LL INF=(LL)1e9+7;
int a[N+2],n,k;
LL dp[N+2][MAXK+2]={},f[N+2][MAXK+2]={};
int32_t main(){
scanf("%d%d",&n,&k);
FOR(i,1,n) scanf("%d",&a[i]);
vector<int>q;
a[0]=INF;q.push_back(0);
memset(dp,0x3f,sizeof dp);
memset(f,0x3f,sizeof f);
dp[0][0]=0;
FOR(i,1,n){
while (q.size()&&a[q.back()]<a[i]) {
FOR(j,1,k) {
f[i][j]=min(f[q.back()][j],f[i][j]);
dp[i][j]=min(f[q.back()][j-1]+a[i],dp[i][j]);
}
q.pop_back();
}
int x=q.back();
FOR(j,1,k){
dp[i][j]=min({dp[i][j],dp[x][j],dp[x][j-1]+a[i]});
f[i][j]=min(f[i][j],dp[i][j]);
}
q.push_back(i);
}
printf("%lld",dp[n][k]);
}
