#include <bits/stdc++.h>
using namespace std;
#define int ll
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pi> vp;
typedef vector<pl> vpl;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cerr.tie(nullptr);
int n, k;
cin >> n >> k;
vi a(n+1, 0);
for (int i = 1; i <= n; ++i)
cin >> a[i];
vector<vi> m(n+1, vi(n+1,0));
for (int i = 1; i <= n; ++i){
m[i][i] = a[i];
for (int j = i+1; j <= n; ++j){
m[i][j] = max(m[i][j-1], a[j]);
}
}
vector<vi> dp(k+1,vi(n+1,INT32_MAX));
for (int i = 1; i <= n; ++i){
dp[1][i] = m[1][i];
}
for (int i = 2; i <= k; ++i){
for (int j = 1; j <= n; ++j){
for (int t = 1; t < j; ++t){
dp[i][j] = min(dp[i-1][t] + m[t+1][j], dp[i][j]);
}
}
}
cout << dp[k][n] << '\n';
}
