#include<bits/stdc++.h>
#define int long long
using namespace std;
int ar[100005];
int dp[105][100005];
int inf=1e15;
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n,k;cin>>n>>k;
for(int i=1;i<=n;i++)cin>>ar[i];
for(int i=0;i<=k;i++)for(int j=0;j<=n;j++)dp[i][j]=inf;
dp[0][0]=0;
ar[0]=inf;
for(int i=1;i<=k;i++){
stack<pair<int,pair<int,int>>>s;
for(int j=i;j<=n;j++){
int mn=dp[i-1][j-1]+ar[j];
//cerr<<"i,j:"<<i<<" "<<j<<' '<<mn<<"\n";
while(!s.empty()&&ar[j]>ar[s.top().first]){
mn=min(mn,s.top().second.second-ar[s.top().first]+ar[j]);
s.pop();
}
//cerr<<"i,j:"<<i<<" "<<j<<' '<<mn<<"\n";
int pmn=mn;
if(!s.empty())pmn=min(mn,s.top().second.first);
dp[i][j]=pmn;
s.push({j,{pmn,mn}});
}
//for(int j=0;j<=n;j++)cerr<<dp[i][j]<<' ';
//cerr<<"\n";
}
cout<<dp[k][n];
}
