#include <bits/stdc++.h>
#define f first
#define s second
#define ll long long
using namespace std;
const int maxn=1e5+5;
const int MOD=1e9+7;
int n,k;
int a[maxn],L[maxn];
ll dp[maxn][105],tree[4*maxn];
stack<int> st;
void update(int id,int l,int r,int pos,ll val)
{
if(pos<l||pos>r) return;
if(l==r){
tree[id]=val;
return;
}
int mid=(l+r)/2;
update(id*2,l,mid,pos,val);
update(id*2+1,mid+1,r,pos,val);
tree[id]=min(tree[id*2],tree[id*2+1]);
}
ll get(int id,int l,int r,int u,int v)
{
if(r<u||v<l) return 1e18;
if(u<=l&&r<=v) return tree[id];
int mid=(l+r)/2;
return min(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
while(!st.empty()&&a[st.top()]<=a[i]) st.pop();
if(!st.empty()) L[i]=st.top()+1;
else L[i]=1;
st.push(i);
}
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++) dp[i][j]=1e18;
}
dp[0][0]=0;
for(int j=1;j<=k;j++){
for(int i=0;i<=n;i++) update(1,0,n,i,dp[i][j-1]);
for(int i=1;i<=n;i++){
dp[i][j]=min(dp[i][j],get(1,0,n,L[i]-1,i-1)+a[i]);
dp[i][j]=min(dp[i][j],dp[L[i]-1][j]);
}
}
cout<<dp[n][k];
}
