#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 15 + 5;
int a[N];
int st[25][N];
int L[N];
int n, k;
int dp[105][N];
int lg[N];
void build() {
for (int i = 1; i <= n; i++) {
st[0][i] = a[i];
}
for (int i = 1; i <= lg[n]; i++) {
for (int j = 1; j + (1 << i) - 1 <= n; j++) {
st[i][j] = max(st[i-1][j], st[i-1][j + (1 << (i-1))]);
}
}
}
inline int get(int l, int r) {
int i = lg[r - l + 1];
return max(st[i][l], st[i][r - (1 << i) + 1]);
}
void dnc(int l, int r, int opl, int opr, int i) {
if (l > r) return;
int ans = 1e18;
int m = (l+r)/2;
int j;
for (int t = opl; t <= min(m, opr); t++) {
int c = dp[i-1][t-1] + get(t, m);
if (c < ans) {
ans = c;
j = t;
}
}
dp[i][m] = min(dp[i][m], ans);
dnc(l, m-1, opl, j, i);
dnc(m+1, r, j, opr, i);
}
signed main() {
cin.tie(0)->sync_with_stdio(false);
for (int i = 2; i < N; i++) lg[i] = lg[i/2] + 1;
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
build();
for (int i = 0; i <= k; i++) {
for (int j = 0; j <= n; j++) {
dp[i][j] = 1e18;
}
}
dp[0][0] = 0;
for (int i = 1; i <= k; i++) {
dnc(1, n, 1, n, i);
}
cout << dp[k][n];
return 0;
}
