/*
Link: https://oj.uz/problem/submit/IZhO14_blocks
*/
#include <bits/stdc++.h>
#define MASK(k) (1LL << (k))
#define BIT(x, i) (((x) >> (i)) & 1)
#define __builtin_popcount __builtin_popcountll
#define __builtin_ctz __builtin_ctzll
#define For(i, a, b) for(int i = (int)(a); i <= (int)(b); ++i)
#define Fod(i, a, b) for(int i = (int)(a); i >= (int)(b); --i)
//#define int long long
#define ll long long
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
#define whole(a) a.begin(), a.end()
#define vi vector<int>
#define ii pair<int, int>
#define pb push_back
#define fi first
#define se second
#define gqt ""
template<class X, class Y>
bool minimize(X& x, const Y& y) {
X eps = 1e-9;
if (x > y + eps) {
x = y;
return true;
}
else return false;
}
template<class X, class Y>
bool maximize(X& x, const Y& y) {
X eps = 1e-9;
if (x + eps < y) {
x = y;
return true;
}
else return false;
}
template<class T>
T Abs(const T& x) {
return (x < 0 ? -x : x);
}
const int INF = 1e9 + 7;
const ll oo = 1e18 + 7;
const int MAX = 1000005;
const int MOD = 1e9 + 7;
using namespace std;
int n, k, a[MAX], dp[105][100005];
void process(){
cin >> n >> k;
For(i, 1, n) cin >> a[i];
memset(dp, 0x3f, sizeof(dp));
dp[1][0] = 0;
For(i, 1, n) dp[1][i] = max(dp[1][i - 1], a[i]);
For(i, 2, k){
stack<ii> st;
For(j, i, n){
int minF = dp[i - 1][j - 1];
while(!st.empty() && a[st.top().se] <= a[j]){
minimize(minF, st.top().fi);
st.pop();
}
dp[i][j] = min(dp[i][st.empty() ? 0 : st.top().se], minF + a[j]);
st.push(ii(minF, j));
}
}
cout << dp[k][n];
}
signed main()
{
fastio
if (fopen(gqt".inp", "r")) {
freopen(gqt".inp", "r", stdin);
freopen(gqt".out", "w", stdout);
}
int Test = 1;
while (Test--) {
process();
}
return 0;
}
