#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ii pair <int, int>
#define ill pair <ll, ll>
#define ild pair <ld, ld>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define file "test"
using namespace std;
const int N = 1e5 + 2;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
const ll base = 311;
const int BLOCK_SIZE = 400;
int n, k;
int a[N], f[N][102];
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; i ++) cin >> a[i];
memset(f, 0x3f3f, sizeof f);
f[0][1] = 0;
for (int i = 1; i <= n; i ++)
f[i][1] = max(f[i - 1][1], a[i]);
for (int j = 2; j <= k; j ++) {
stack <ii> h;
for (int i = j; i <= n; i ++) {
int cur = f[i - 1][j - 1];
while (!h.empty() && a[h.top().se] <= a[i]) {
cur = min(cur, h.top().fi);
h.pop();
}
f[i][j] = min(f[(h.empty() ? 0 : h.top().se)][j], cur + a[i]);
h.push({cur, i});
}
}
cout << f[n][k];
}
/*
/\_/\ zzZ
(= -_-)
/ >u >u
*/
