#include<stdio.h>
int max(int a, int b){return a>b?a:b;}
int min(int a, int b){return a<b?a:b;}
int dp[101][100001];
int IT[300001];
int b = 1;
int a[100001];
void setT(int *dest, int *src, int s, int e, int f, int r);
int getmax(int f, int r)
{
f+=b; r+=b;
int re = 0;
while(f<r)
{
if(f%2 == 1) re = max(re, IT[f++]);
if(r%2 == 0) re = max(re, IT[r--]);
f/=2; r/=2;
}
if(f==r) re = max(re, IT[f]);
return re;
}
int main()
{
int n, k;
int i, j;
scanf("%d%d", &n, &k);
for(b=1; b<=n; b*=2);
for(i=1; i<=n; i++)
{
scanf("%d", a+i);
IT[b+i] = a[i];
}
for(i=b; i>=1; i--) IT[i] = max(IT[i*2], IT[i*2+1]);
for(i=1; i<=n; i++) dp[1][i] = getmax(1, i);
for(i=2; i<=k; i++)
{
for(j=i; j<=n; j++)
{
dp[i][j] = dp[i-1][i-1] + getmax(i, j);
for(int k=i; k<=j-1; k++) dp[i][j] = min(dp[i][j], dp[i-1][k] + getmax(k+1, j));
}
}
printf("%d", dp[k][n]);
return 0;
}
