#include <bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); i++)
#define R(i, j, k) for(int i = (j); i >= (k); i--)
#define all(x) x.begin(), x.end()
#define sz(a) ((int) a.size())
#define pb emplace_back
#define fst first
#define snd second
using namespace std;
typedef long long ll;
const int INF=1e9,MAXN=1e5+5;
void chmin(int &a,int b){a=min(a,b);}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,k;cin>>n>>k;
vector<int> a(n);
L(i,0,n-1)cin>>a[i];
vector<vector<int>>dp(k+1,vector<int>(n+1,INF));
dp[0][0]=0;
//dp[i][j]=min(dp[i-1][t]+max(a[t...j-1]));
L(i,1,k){
stack<pair<int,int>>st;
L(j,i-1,n-1){
int ndp=dp[i-1][j];
while(sz(st)&&a[st.top().fst]<=a[j]){
chmin(ndp,st.top().snd);
st.pop();
}
if(a[j]+ndp<a[st.top().fst]+st.top().snd)st.push({j,ndp});
chmin(dp[i][j+1],a[st.top().fst]+st.top().snd);
}
}
cout<<dp[k][n]<<endl;
}
