#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define fi first
#define se second
#define ll long long
using namespace std;
const int N = 1e3 + 7;
const int mod = 1e9 + 7;
int n,k;
int a[N];
int d[N][N];
void solve()
{
cin >> n >> k;
for( int i = 1; i <= n; i++ ){
cin >> a[i];
d[1][i] = a[i];
}
for( int i = 1; i <= n; i++ ){
for( int j = 1; j <= n; j++ ){
d[i][j] = 1e9;
}
}
for( int i = 1; i <= n; i++ ){
for( int j = 1; j <= k; j++ ){
int sum = 0;
for( int h = i; h >= j; h-- ){
sum = max( sum , a[h] );
d[i][j] = min( d[h - 1][j - 1] + sum , d[i][j] );
}
}
}
cout << d[n][k];
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
//freopen( "input.txt" , "r" , stdin );
//freopen( "output.txt" , "w" , stdout );
int t = 1;//cin >> t;
while( t-- ){
solve();
}
}
