#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;
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 id=i-1;
if(!s.empty())id=s.top().first;
int cost=dp[i-1][id]+ar[j];
ms.insert(cost);
s.push({j,cost});
dp[i][j]=*ms.begin();
}
//for(int j=0;j<=n;j++)cerr<<dp[i][j]<<' ';
//cerr<<"\n";
}
cout<<dp[k][n];
}
