#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 1e16;
struct spar{
vector<vector<int>> sp;
int n;
spar(vector<int> a){
n = a.size();
sp.resize(n + 1, vector<int> (22, 0));
for(int i = 1; i <= n; i++)sp[i][0] = a[i-1];
for(int l = 1; l < 22; l ++ ){
int len = (1<<(l-1));
for(int i = 1; i <= n; i++){
sp[i][l] = max(sp[i][l-1], sp[min(n, i + len)][l-1]);
}
}
};
int get(int l, int r){
int lg = __lg(r-l+1);
r = r - (1<<lg) + 1;
return max(sp[l][lg], sp[r][lg]);
};
};
signed main(){
int n, k;
cin >> n >> k;
vector<int> a(n);
for(int & i : a)cin >> i;
vector< vector<int> > dp( n + 1, vector<int> (k + 1, inf));
spar sp(a);
for(int i = 1; i <= n; i++){
dp[i][1] = sp.get(1, i);
}
for(int i = 1; i <= n; i++){
for(int x = 1; x < i; x++){
for(int j = 2; j <= k; j++){
dp[i][k] = min(dp[i][k], dp[x][k-1] + sp.get(x + 1, i));
}
}
}
cout << dp[n][k] << '\n';
};
