/// 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;
struct Node{
int mn, lz, f;
Node(){
this->mn = INF;
this->lz = 0;
this->f = INF;
}
};
struct SMT{
int n;
vector<Node> tree;
SMT(int n=0){
this->n = n;
this->tree.assign(n<<2|1, Node());
}
void down(int id){
if(tree[id].lz == 0) return;
int ID = id<<1;
int &val = tree[id].lz;
tree[ID].lz = val;
tree[ID].mn = tree[ID].f + val;
tree[ID|1].lz = val;
tree[ID|1].mn = tree[ID|1].f + val;
val = 0;
}
void pointUpd(int pos, int val){
int id = 1;
for(int lo=1, hi=n; lo<hi;){
down(id);
int mid = (lo+hi)>>1;
if(pos<=mid) hi = mid, id = id<<1;
else id = id<<1|1, lo = mid + 1;
}
tree[id].f = tree[id].mn = val;
for(id>>=1; id; id>>=1){
tree[id].f = min(tree[id<<1].f, tree[id<<1|1].f);
tree[id].mn = min(tree[id<<1].mn, tree[id<<1|1].mn);
}
}
void rangeUpd(int l, int r, int id, const int &u, const int &v, int val){
if(l>v || r<u) return;
if(l>=u && r<=v){
tree[id].mn = val + tree[id].f;
tree[id].lz = val;
return;
}
down(id);
int mid = (l+r)>>1;
int ID = id<<1;
rangeUpd(l, mid, ID, u, v, val);
rangeUpd(mid+1, r, ID|1, u, v, val);
tree[id].mn = min(tree[ID].mn, tree[ID|1].mn);
}
void rangeUpd(int l, int r, int val){
rangeUpd(1, n, 1, l, r, val);
}
int get(){
return tree[1].mn;
}
};
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;
SMT smt(n);
a[j-1] = INF;
st.push(j-1);
for(int i=j; i<=n; i++){
while(a[st.top()] <= a[i]) st.pop();
smt.pointUpd(i, pre[i-1]);
smt.rangeUpd(st.top()+1, i, a[i]);
cur[i] = smt.get();
st.push(i);
}
for(int i=j; i<=n; i++) pre[i] = cur[i];
}
cout << pre[n];
}
int32_t main(){
fastIO;
//file(TASK);
nhap();
solve();
return 0;
}
