#include <map>
#include <vector>
#include <iostream>
using namespace std;
int mx[100][100];
int dp[100][100][100];
int a[100];
int32_t main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, K;
cin >> n >> K;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int l = 0; l < n; l++) {
for (int r = l; r < n; r++) {
mx[l][r] = a[l];
for (int i = l + 1; i <= r; i++) {
mx[l][r] = max(mx[l][r], a[i]);
}
}
}
for (int i = 0; i < 100; i++) {
for (int j = 0; j < 100; j++) {
for (int _k = 0; _k < 100; _k++) {
dp[i][j][_k] = 2e9;
}
}
}
int ans = 2e9;
for (int i = 0; i < n; i++) {
dp[0][i][0] = mx[0][i];
if (0 == K - 1 && i == n - 1) {
ans = min(ans, dp[0][i][0]);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
for (int k = 0; k <= j - 1; k++) {
for (int _k = 1; _k < K; _k++) {
dp[j][i][_k] = min(dp[j][i][_k], dp[k][j - 1][_k - 1] + mx[j][i]);
if (_k == K - 1 && i == n - 1) {
ans = min(ans, dp[j][i][_k]);
}
}
}
}
}
cout << ans << '\n';
return 0;
}
