#include <bits/stdc++.h>
#define DIM 100010
#define DIMK 110
#define INF 2000000000000000000LL
using namespace std;
int v[DIM],rmq[20][DIM],p[DIM];
long long dp[DIMK][DIM];
int n,k,i,j,t;
int get_min (int x, int y){
int nr = p[y-x+1];
return max (rmq[nr][x],rmq[nr][y-(1<<nr)+1]);
}
void divide (int st, int dr, int opt_st, int opt_dr){
if (st > dr)
return;
int mid = (st+dr)>>1;
long long mini = INF; int opt_mid = 0;
for (int i=opt_st;i<=min(mid-1,opt_dr);i++){
int val = get_min (i+1,mid);
if (dp[j-1][i] + val < mini){
mini = dp[j-1][i] + val;
opt_mid = i;
}
}
dp[j][mid] = mini;
divide (st,mid-1,opt_st,opt_mid);
divide (mid+1,dr,opt_mid,opt_dr);
}
int main (){
//ifstream cin ("date.in");
//ofstream cout ("date.out");
cin>>n>>k;
for (i=1;i<=n;i++){
cin>>v[i];
rmq[0][i] = v[i];
}
for (i=1;(1<<i)<=n;i++)
for (j=1;j<=n;j++){
rmq[i][j] = rmq[i-1][j];
if (j + (1<<(i-1)) <= n)
rmq[i][j] = max (rmq[i][j],rmq[i-1][j + (1<<(i-1))]);
}
for (i=2;i<=n;i++)
p[i] = p[i/2] + 1;
for (i=1;i<=k;i++)
for (j=1;j<=n;j++)
dp[i][j] = INF;
int maxi = 0;
for (i=1;i<=n;i++){
maxi = max (maxi,v[i]);
dp[1][i] = maxi;
}
/// dp[j][i] <= dp[j][i+1]
if (n > 100){
for (j=2;j<=k;j++)
divide (1,n,1,n);
} else {
for (j=2;j<=k;j++){
for (i=j;i<=n;i++){
/// dp[j][i] = min (dp[k][i] + max(k+1..i))
int maxi = 0;
for (t=i;t>1;t--){
maxi = max (maxi,v[t]);
dp[j][i] = min (dp[j][i],dp[j-1][t-1] + maxi);
}}}}
cout<<dp[k][n];
return 0;
}
