#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define left _left
#define right _right
#define ll long long
#define sz(s) ((int)(s).size())
#define ALL(v) (v).begin(), (v).end()
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define REP(i, a, b) for (int i = (a); i >= (b); --i)
#define FOREACH(x, a) for (auto x : (a))
#define MASK(i) (1LL << (i))
#define BIT(mask, i) (((mask) >> (i)) & 1LL)
#define popcount __builtin_popcountll
template<class T1, class T2> inline bool maximize(T1 &x, T2 y) {
T1 EPS = 1e-9;
if (x + EPS < y) return x = y, true;
return false;
}
template<class T1, class T2> inline bool minimize(T1 &x, T2 y) {
T1 EPS = 1e-9;
if (x > y + EPS) return x = y, true;
return false;
}
template<class T> inline vector<T> remove_duplicate(vector<T> a) {
sort(ALL(a)); a.resize(unique(ALL(a))-a.begin());
return a;
}
#define TASK "elecar"
void online() {
freopen(TASK".inp", "r", stdin);
freopen(TASK".out", "w", stdout);
}
const ll oo = 4e18 + 7;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const int MAX = (int) 1e5 + 5;
int n, k;
ll a[MAX];
namespace sub_one {
void perform() {
#define Fast vector<vector<ll>>
Fast dp(n+1, vector<ll>(k+1, oo));
Fast max_cost(n+1, vector<ll>(n+1, 0));
FOR(i, 1, n) FOR(j, i, n) {
if (i == j)
max_cost[i][j] = a[j];
else max_cost[i][j] = max(max_cost[i][j-1], a[j]);
}
dp[0][0] = 0;
FOR(i, 1, n) FOR(j, 1, k) {
FOR(r, 0, i-1) {
minimize(dp[i][j], dp[r][j-1] + max_cost[r+1][i]);
}
}
cout << dp[n][k] << "\n";
}
}
signed main(void) {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> k;
FOR(i, 1, n) cin >> a[i];
#define CHECK 25000000
if (n * k <= CHECK)
return sub_one::perform(), 0;
return 0;
}
