#include <bits/stdc++.h>
#define pb push_back
#define s second
#define f first
#define ll long long
#define left (node<<1),l,((l+r)>>1)
#define right ((node<<1)|1),((l+r)>>1) + 1,r
using namespace std;
const int N = 100005;
int dp[N][105],a[N],sgt[4*N];
void build(int node,int l,int r){
if (l == r) {sgt[node] = a[l]; return;}
build(left),build(right);
sgt[node] = max(sgt[(node<<1)],sgt[((node<<1)|1)]);
}
int get(int node,int l,int r,int L,int R){
if (r < L || R < l) return 0;
if (L <= l && r <= R) return sgt[node];
int x = get(left,L,R),y = get(right,L,R);
return max(x,y);
}
main (){
ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
int n,k;
cin>>n>>k;
for (int i = 1; i <= n; i++)
cin>>a[i];
build(1,1,n);
for (int i = 1; i <= n; i++)
for (int j = 0; j <= k; j++)
dp[i][j] = 1e9;
for (int i = 1; i <= n; i++){
for (int j = 1; j < i; j++)
for (int K = 2; K <= k; K++)
dp[i][K] = min(dp[i][K],dp[j][K - 1] + get(1,1,n,j + 1,i));
dp[i][1] = get(1,1,n,1,i);
}
cout<<dp[n][k];
}
