#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for(ll i=ll(a); i<ll(b); i++)
#define repn(i, a, b) for(ll i=ll(b)-1; i>=ll(a); i--)
#define pb push_back
#define si size()
#define ff first
#define ss second
#define be begin()
#define en end()
const ll N=(1e5)+1;
const ll K=101;
const ll inf=(1e8)+1;
vector<ll> v(N);
vector<ll> x(N, -1);
vector<ll> s;
vector<ll> dp1(N, inf), dp2(N, inf);
vector<ll> T(2*N, inf);
void construct(ll n){
rep(i, 0, n){
T[n+i]=v[i];
}
repn(i, 1, n){
T[i]=min(T[2*i], T[2*i+1]);
}
}
void upd(ll in, ll val, ll n){
in+=n;
T[in]=val;
while(in>1){
in/=2;
T[in]=min(T[2*in], T[2*in+1]);
}
}
ll que(ll l, ll r, ll n){
l+=n, r+=n;
ll mn=inf;
while(l<r){
if(l%2==1){
mn=min(mn, T[l]);
l++;
}
if(r%2==1){
r--;
mn=min(mn, T[r]);
}
l/=2;
r/=2;
}
return mn;
}
void solve(){
ll n, k;
cin>>n>>k;
rep(i, 0, n){
cin>>v[i];
}
ll o=0;
s.pb(1);
rep(i, 1, n){
if(v[s[o]]>=v[i]){
x[i]=s[o];
}
else{
while(true){
if(o<0) break;
if(v[s[o]]>=v[i]) break;
s.pop_back();
o--;
}
if(o!=-1){
x[i]=s[o];
}
}
o++;
s.pb(i);
}
dp1[0]=v[0];
upd(0, dp1[0], n);
rep(i, 1, n){
dp1[i]=max(dp1[i-1], v[i]);
upd(i, dp1[i], n);
}
rep(j, 2, k+1){
rep(i, 0, n){
dp2[i]=inf;
if(i+1<j){
continue;
}
else{
dp2[i]=v[i]+dp1[i-1];
if(x[i]==-1){
dp2[i]=min(dp2[i], v[i]+que(0, i-1, n));
}
else if(x[i]==i-1){
dp2[i]=min(dp2[i], dp2[x[i]]);
}
else{
dp2[i]=min(dp2[i], v[i]+que(x[i]+1, i-1, n));
dp2[i]=min(dp2[i], dp2[x[i]]);
}
}
}
rep(i, 0, n){
upd(i, dp2[i], n);
}
swap(dp1, dp2);
}
cout<<dp1[n-1];
}
int main(){
ios_base::sync_with_stdio();
cin.tie(0);
ll t=1;
//~ cin>>t;
while(t--){
solve();
}
return 0;
}
