#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,fen[1000009],f[100009],k[100009];
long long dp[100009][109],pr[100009][109];
stack <int> s;
void upd(int q, int w){
while(q<=1000002){
fen[q]=max(fen[q],w);
q=q+(q&(-q));
}
}
int read(int q){
int jm=0;
while(q>=1){
if(jm<fen[q]) jm=fen[q];
q=q-(q&(-q));
}
return jm;
}
int main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
/*printf("%d%d",&a,&b);
scanf("\n");*/
cin>>a>>b;
for(i=1; i<=a; i++){
cin>>f[i];
//scanf("%d",&f[i]);
//k[i]=read(1000001-f[i]);
//cout<<k[i]<<" ";
//upd(1000001-f[i]+1,i);
}
//cout<<endl;
zx=0;
for(i=0; i<=a; i++){
for(j=0; j<=b; j++) pr[i][j]=999999999999999999LL;
for(j=0; j<=b; j++) dp[i][j]=999999999999999999LL;
}
dp[0][0]=0;zx=0;
for(i=1; i<=a; i++){
while(s.size()>0&&f[s.top()]<f[i]){
for(j=1; j<b; j++){
pr[i][j]=min(pr[i][j],pr[s.top()][j]-f[s.top()]+f[i]);
}
s.pop();
}
if(s.size()>0){
for(j=1; j<b; j++){
pr[i][j]=min(pr[i][j],pr[s.top()][j]);
}
}
for(j=1; j<b; j++){
pr[i][j]=min(pr[i][j],dp[i-1][j]+f[i]);
}
for(j=2; j<=b; j++){
dp[i][j]=dp[i-1][j-1]+f[i];
if(dp[i][j]>pr[i][j-1]) dp[i][j]=pr[i][j-1];
}
zx=max(zx,f[i]);
dp[i][1]=zx;
s.push(i);
}
//cout<<pr[1][1]<<endl;
cout<<dp[a][b];
return 0;
}
