#include <bits/stdc++.h> #define L(i, j, k) for(int i = (j); i <= (k); i++) #define R(i, j, k) for(int i = (j); i >= (k); i--) #define ll long long #define sz(a) ((int) a.size()) #define all(a) a.begin(), a.end() #define vi vector<int> #define pb emplace_back #define me(a, x) memset(a, x, sizeof(a)) #define fst first #define snd second #define ii pair<int, int> using namespace std; const int inf=1e9; void chmin(int &a,int b){ a=min(a,b); } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n,K;cin>>n>>K; vi a(n); L(i,0,n-1)cin>>a[i]; vector<vi>dp(n+1,vi(K+1,inf)); dp[0][0]=0; L(i,0,n-1){ int maxRange=0; L(j,i,n-1){ maxRange=max(maxRange,a[j]); L(k,1,K){ chmin(dp[j+1][k],maxRange+dp[i][k-1]); } } } cout<<dp[n][K]<<endl; }