#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double
const int MAXN = 1e6;
const ll INF = 4e18;
const int MOD = 998244353;
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tc = 1;
// cin >> tc;
for(;tc--;){
ll N, K; cin >> N >> K;
vector<ll> a(N + 5), lf(N + 5, 1), rg(N + 5, N);
for(int i = 1; i <= N; i++) cin >> a[i];
vector<ll> dp(N + 5, INF);
dp[0] = 0;
for(int i = 1; i <= K; i++){
stack<pii> stk;
vector<ll> ndp(N + 5, INF);
for(int j = 1; j <= N; j++){
ll cur = dp[j - 1];
while(!stk.empty() && a[stk.top().fi] <= a[j]){
cur = min(cur, stk.top().sec);
stk.pop();
}
// bikin segment baru
ndp[j] = cur + a[j];
// gabung dengan segment sebelumnya
if(!stk.empty()) ndp[j] = min(ndp[j], ndp[stk.top().fi]);
stk.push({j, cur});
}
dp.swap(ndp);
}
cout << dp[N] << "\n";
}
}
/*
1 2 3 4 5 6 7
*/
