#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];
vector<ll>add[100023],sub[100023];
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++){
map<ll,int>mp;
for(int j=1;j<=n+1;j++){
for(ll x:add[j]){
mp[x]++;
}
add[j].clear();
for(ll x:sub[j]){
if(!--mp[x])mp.erase(x);
}
sub[j].clear();
if(mp.size())dp[j][i]=min(dp[j][i],mp.begin()->fr);
if(j==n+1)continue;
if(nex[j]!=n+1){
dp[nex[j]][i]=min(dp[nex[j]][i],dp[j][i]);
}
}
for(int j=1;j<=n;j++){
add[j+1].pb(dp[j][i]+arr[j]);
if(nex[j]!=n+1){
sub[nex[j]+1].pb(dp[j][i]+arr[j]);
}
}
}
cout<<dp[n+1][k];
}
