#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,int>>s;
multiset<int>ms;
s.push({i-1,inf});
for(int j=i;j<=n;j++){
/*while(!s.empty()&&ar[s.top().first]<=ar[j])ms.erase(ms.lower_bound(s.top().second)),s.pop();
int cost=dp[i-1][s.top().first]+ar[j];
ms.insert(cost);
s.push({j,cost});
dp[i][j]=*ms.begin();*/
int mx=ar[j];
for(int l=j-1;l>=i-1;l--){
dp[i][j]=min(dp[i][j],dp[i-1][l]+mx);
mx=max(mx,ar[l]);
}
}
//for(int j=0;j<=n;j++)cerr<<dp[i][j]<<' ';
ar[i]=inf;
//cerr<<"\n";
}
cout<<dp[k][n];
}
