#include"bits/stdc++.h"
using namespace std;
#define ll long long
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false)
#define inf LLONG_MAX
const int lmt=1e5+10;
ll dp[lmt][101];
int main(){
fastio;
for(int i=0;i<lmt;i++){
for(int j=2;j<101;j++) dp[i][j]=1e12;
}
int n,k;
cin>>n>>k;
ll a[n+1];
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
dp[i][1]=max(dp[i-1][1],a[i]);
}
for(int j=2;j<=k;j++){
stack<pair<int,ll>>s;
for(int i=1;i<=n;i++){
ll mn=1e12;
while(!s.empty() && a[s.top().first]<=a[i]){
mn=min(mn,s.top().second);
s.pop();
}
dp[i][j]=min(dp[i][j],mn+a[i]);
if(!s.empty()){
dp[i][j]=min(dp[i][j],dp[s.top().first][j-1]+a[i]);
dp[i][j]=min(dp[i][j],dp[s.top().first][j]);
}
mn=min(mn,dp[i][j-1]);
s.push({i,mn});
}
}
cout<<dp[n][k]<<endl;
return 0;
}
