#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;
int mx = 0;
for( int i = 1; i <= n; i++ ){
cin >> a[i];
mx = max( mx , a[i] );
d[1][i] = mx;
}
for( int i = 2; i <= k; i++ ){
for( int j = 1; j <= n; j++ ){
d[i][j] = 1e9;
}
}
for( int i = 2; i <= n; i++ ){
for( int j = 2; j <= k; j++ ){
int sum = 0;
for( int h = i; h <= n; h++ ){
sum = max( sum , a[h] );
d[j][h] = min( d[j - 1][i - 1] + sum , d[j][h] );
}
}
}
/*
for( int i = 2; i <= k; i++ ){
for( int j = i; j <= n; j++ ){
int mx = 0;
for( int h = j; h <= n; h++ ){
mx = max( mx , a[h] );
d[i][h] = min( d[i][h] , d[i - 1][j - 1] + mx );
}
}
}
*/
cout << d[k][n];
}
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();
}
}
