#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const char el = '\n';
const int maxn = 1e6+7;
const int logn = 21;
const ll inf = 1e16+7;
int n, k;
int a[maxn];
int spt[logn][maxn];
ll dp[2][maxn];
template<typename T>
void print(T a[], int n) { for (int i = 0; i < n; i++) cout << a[i] << ' '; cout << el; }
void build_spt() {
for (int i = 1; i <= n; i++) spt[0][i] = a[i];
for (int i = 1; i < logn; i++) {
int p = 1<<i;
int q = p>>1;
if (p > n) break;
for (int j = 1; j+p-1 <= n; j++) {
int a = spt[i-1][j];
int b = spt[i-1][j+q];
spt[i][j] = max(a, b);
}
}
}
int get(int l, int r) {
if (l > r) swap(l, r);
int k = __lg(r-l+1);
int a = spt[k][l];
int b = spt[k][r-(1<<k)+1];
return max(a, b);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
// freopen("test.inp", "r", stdin);
// freopen(".inp", "r", stdin);
// freopen(".out", "w", stdout);
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
build_spt();
for (int i = 0; i<2; i++) fill(dp[i], dp[i]+n+1, inf);
int c = 1;
dp[c&1][0] = 0;
for (int i = 1; i <= n; i++) dp[c&1][i] = get(1, i);
c++;
for (; c <= k; c++) {
int cur = c&1, prev = cur^1;
fill(dp[cur], dp[cur]+n+1, inf);
dp[cur][0] = 0;
for (int i = 1; i <= c; i++) dp[cur][i] = dp[cur][i-1] + a[i];
for (int i = c+1; i <= n; i++)
for (int j = i; j >= c; j--)
dp[cur][i] = min(dp[cur][i], get(i, j) + dp[prev][j-1]);
}
cout << dp[k&1][n];
return 0;
}
