//https://oj.uz/submission/1186122
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;
const ll inf=1000000000000;
int n,k;
ll arr[100023];
int nex[100023];
ll dp[100023][101];
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);
cin>>n>>k;
for(int i=1;i<=n+1;i++){
for(int j=0;j<=k;j++){
dp[i][j]=inf;
}
}
dp[1][0]=0;
for(int i=1;i<=n;i++){
cin>>arr[i];
}
arr[n+1]=inf;
vector<int>sta={n+1};
for(int i=n;i>=1;i--){
while(arr[sta.back()]<=arr[i]){
sta.pop_back();
}
nex[i]=sta.back();
sta.pb(i);
}
for(int i=0;i<=k;i++){
vector<pair<int,ll>>v;
for(int j=1;j<=n+1;j++){
if(v.size()){
dp[j][i]=min(dp[j][i],v.back().sc);
}
while(v.size()&&arr[v.back().fr]<arr[j]){
v.pop_back();
}
if(i){
v.pb({j,dp[j][i-1]});
if(v.size()>1){
v.back().sc=min(v.back().sc,v[v.size()-2].sc);
}
}
if(j==n+1)continue;
if(nex[j]!=n+1){
dp[nex[j]][i]=min(dp[nex[j]][i],dp[j][i]);
}
dp[j][i]+=arr[j];
}
}
cout<<dp[n+1][k];
}
