#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define FOR(a , b) for(int i = a;i <= b;i++)
#define pb push_back
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int INF = 1e18;
const int mod = 1e9 + 7;
const int N = 1e5 + 1;
int n , k , a[N] , st[N * 4];
void build(int idx , int l , int r)
{
if(l == r){
st[idx] = a[l];
return;
}
int mid = (l + r) >> 1;
build(2 * idx , l , mid);
build(2 * idx + 1 , mid + 1 , r);
st[idx] = max(st[2 * idx] , st[2 * idx + 1]);
}
int ask(int idx , int l , int r , int ql , int qr)
{
if(ql > r or l > qr) return -INF;
else if(ql <= l && r <= qr){
return st[idx];
}
int mid = (l + r) >> 1;
return max(ask(2 * idx , l , mid , ql , qr) , ask(2 * idx + 1 , mid + 1 , r , ql , qr));
}
int get(int l , int r)
{
if(l > r) return 0;
return ask(1 , 1 , n , l , r);
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin >> n >> k;
int MX = -1;
for(int i = 1;i <= n;i++)
{
cin >> a[i];
MX = max(MX , a[i]);
}
if(k == 1)
{
cout << MX << endl;
return 0;
}
build(1 , 1 , n);
vector < vector < int > > dp(k , vector < int > (n + 1 , INF));
for(int i = 1;i <= n;i++)
{
int q = (n - i);
if(q + 1 < k) continue;
dp[1][i] = get(1 , i);
}
for(int c = 2;c <= k - 1;c++)
{
for(int i = c;i <= n;i++)
{
int q = (n - i);
if(c + q < k) continue;
for(int j = c - 1;j <= i - 1;j++)
{
int Q = (n - j);
int C = c - 1;
if(C + Q < k) continue;
dp[c][i] = min(dp[c][i] , dp[c - 1][j] + get(j + 1 , i));
}
}
}
int res = INF;
for(int i = 1;i <= n;i++)
{
res = min(res , dp[k - 1][i] + get(i + 1 , n));
}
cout << res << endl;
}
