/// dwuy: _,\,,,_\,__,\,,_
#include <bits/stdc++.h>
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) int32_t(s.length())
#define MASK(k)(1LL<<(k))
#define TASK ""
using namespace std;
typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;
const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MX = 100005;
int n, k;
int a[MX];
int cur[MX];
int pre[MX];
void nhap(){
cin >> n >> k;
for(int i=1; i<=n; i++) cin >> a[i];
}
void solve(){
for(int i=1, mx=0; i<=n; i++){
mx = max(mx, a[i]);
pre[i] = mx;
}
for(int j=2; j<=k; j++){
stack<int> st, mn, mnf;
a[j-1] = INF;
st.push(j-1);
mn.push(INF);
mnf.push(INF);
for(int i=j; i<=n; i++){
int val = pre[i-1];
while(a[st.top()] <= a[i]){
st.pop();
mn.pop();
val = min(val, mnf.top());
mnf.pop();
}
mn.push(min(mn.top(), val+a[i]));
mnf.push(val);
st.push(i);
cur[i] = mn.top();
}
for(int i=j; i<=n; i++) pre[i] = cur[i];
}
cout << pre[n];
}
int32_t main(){
fastIO;
//file(TASK);
nhap();
solve();
return 0;
}
/**
5 3
5 7 10 3 5
**/
