#include <iostream>
#define MAXN 100005
#define intt long long
using namespace std ;
intt n , k , a[MAXN] , dp[MAXN][105] , q[MAXN][105] ;
int main () {
cin >> n >> k ;
for ( int i = 1 ; i <= n ; i ++ ) cin >> a[i] ;
for ( int i = 1 ; i <= n ; i ++ )
for ( int v = 1 ; v <= k ; v ++ ) dp[i][v] = 343334344 ;
dp[1][1] = a[1] ;
for ( intt i = 2 ; i <= n ; i ++ ) {
dp[i][1] = max ( dp[i - 1][1] , a[i] ) ;
for ( int v = 2 ; v <= min ( i , k ) ; v ++ ) {
intt mx = 0 ;
dp[i][v] = dp[i - 1][v - 1] + a[i] ;
for ( int j = i - 1 ; j >= 1 ; j -- ) {
if ( j < v - 1 ) break ;
mx = max ( mx , a[j + 1] ) ;
if ( dp[i][v] > dp[j][v - 1] + mx ) dp[i][v] = dp[j][v - 1] + mx ;
}
}
}
cout << dp[n][k] << endl ;
return 0 ;
}
