#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sz(v) (int)v.size()
const int MAXN = 1e5+5;
const ll INF = 1e14;
int a[MAXN];
ll dp[2][MAXN];
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n,K; cin>>n>>K;
for(int i = 1; i <= n; i++)cin>>a[i];
for(int i = 1; i <= n; i++)dp[0][i] = INF; dp[0][n+1] = 0;
for(int k = 1; k <= K; k++){
vector<int> p; vector<ll> pmn;
multiset<ll> st;
dp[k&1][n+1] = INF;
for(int i = n; i >= 1; i--){
ll mn = dp[(k-1)&1][i+1];
while(sz(p) > 0 && a[p.back()] <= a[i]){
mn = min(mn, pmn.back());
st.erase( st.find(pmn.back() + a[p.back()]) );
p.pop_back(); pmn.pop_back();
}
p.push_back(i); pmn.push_back(mn);
st.insert(mn + a[i]);
dp[k&1][i] = min(INF,*st.begin());
}
}
cout<<dp[K&1][1]<<"\n";
}
