#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define db(val) "[" #val " = " << (val) << "] "
const ll mod = 1e9 + 7;
const int maxn = 1e5 + 4;
const int INF = 1e9;
const int N = 18;
int n, k, a[maxn], dp[maxn][105], spt[maxn][20];
int get(int l, int r) {
int j = __lg(r - l + 1);
return max(spt[l][j], spt[r - (1 << j) + 1][j]);
}
void Solve(int l, int r, int optL, int optR, int k) {
if (l > r) return;
int m = (l + r) / 2, opt = optL;
for (int i = optL; i <= min(m - 1, optR); i++) {
if (dp[i][k - 1] + get(i + 1, m) < dp[m][k]) {
dp[m][k] = dp[i][k - 1] + get(i + 1, m);
opt = i;
}
}
Solve(l, m - 1, optL, opt, k);
Solve(m + 1, r, opt, optR, k);
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
//freopen("BLOCKS.INP", "r", stdin);
//freopen("BLOCKS.OUT", "w", stdout);
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
spt[i][0] = a[i];
}
for (int j = 1; j <= N; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++)
spt[i][j] = max(spt[i][j - 1], spt[i + (1 << (j - 1))][j - 1]);
memset(dp, 63, sizeof dp);
for (int i = 1; i <= n; i++)
dp[i][1] = get(1, i);
if (n <= 100) {
for (int t = 2; t <= k; t++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j < i; j++) {
if (dp[j][t - 1] + get(j + 1, i) < dp[i][t]) {
dp[i][t] = dp[j][t - 1] + get(j + 1, i);
}
}
}
}
}
else {
for (int t = 2; t <= k; t++)
Solve(1, n, 1, n, t);
}
cout << dp[n][k];
}
