#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
void solve(){
int n, k;
cin >> n >> k;
vector<ll> a(n+1);
for(int i = 1; i <= n; i++){
cin >> a[i];
}
vector<ll> f(n+1, INF), prv(n+1, INF);
f[0] = 0;
a[0] = INF;
for(int j = 1; j <= k; j++){
prv = f;
fill(f.begin(), f.end(), INF);
stack<pair<int, ll>> st;
for(int i = 1; i <= n; i++){
ll mnf = prv[i-1];
while(!st.empty() && a[st.top().first] <= a[i]){
mnf = min(mnf, st.top().second);
st.pop();
}
f[i] = min(f[st.empty() ? 0 : st.top().first], mnf + a[i]);
st.push({i, mnf});
}
}
cout << f[n];
}
void trau(){
int n, k;
cin >> n >> k;
vector<ll> a(n+1);
for(int i = 1; i <= n; i++){
cin >> a[i];
}
vector<ll> f(n+1, INF), prv(n+1, INF);
f[0] = 0;
a[0] = INF;
for(int j = 1; j <= k; j++){
prv = f;
fill(f.begin(), f.end(), INF);
stack<pair<int, ll>> st;
st.push({0, INF});
for(int i = 1; i <= n; i++){
ll mx = 0;
for(int l = i; l >= 1; l--){
mx = max(mx, a[l]);
f[i] = min(f[i], prv[l-1]+mx);
}
}
}
cout << f[n];
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//freopen("main.inp", "r", stdin);
//freopen("main.out", "w", stdout);
solve();
}
