#include <bits/stdc++.h>
#define fr first
#define sc second
#define OK puts("OK");
#define pb push_back
#define mk make_pair
using namespace std;
typedef long long ll;
const int inf = (int)1e9 + 7;
const int N = (int)1e5 + 2;
int n,kk;
int dp[2][N];
int a[N];
int t[21][N];
void buildtable() {
for (int i = 0; i <= log2(n); i ++) {
for (int j = 1; j <= n; j ++) {
if (i == 0) {
t[i][j] = a[j];
continue;
}
t[i][j] = max(t[i - 1][j],t[i - 1][j + (1 << (i - 1))]);
}
}
}
int get (int l,int r) {
int cur = log2(r - l + 1);
return max(t[cur][l],t[cur][r - (1 << cur) + 1]);
}
void compute (int k,int l,int r,int L,int R) {
if (l > r)
return;
int m = (r + l) / 2;
int opt = -1;
dp[k & 1][m] = inf;
int &d = dp[k & 1][m];
for (int i = L; i <= min(m,R); i ++) {
int now = dp[(k & 1) ^ 1][i - 1] + get(i,m);
if (now < d)
d = now,opt = i;
}
compute (k,l,m - 1,L,opt);
compute (k,m + 1,r,opt,R);
}
main () {
cin >> n >> kk;
for (int i = 1; i <= n; i ++)
cin >> a[i];
buildtable();
for (int i = 1; i <= n; i ++)
dp[1][i] = get(1,i);
for (int i = 2; i <= kk; i ++)
compute (i,i,n,i,n);
cout << dp[kk & 1][n] << endl;
}
