#include<iostream> #include<vector> #include<algorithm> #include<string> #include<cmath> #include<set> #include<map> #include<queue> #include<stack> #include<unordered_map> using namespace std; using ll = long long; ll mod = 1e18; ll gcd(ll a, ll b) { if (b != 0) { return gcd(b, a % b); } else return a; } ll lcm(ll a, ll b) { return a * b / gcd(a, b); } ll pv(ll a, ll b) { if (b == 0)return 1; ll res = pv(a, b / 2) % mod; if (b % 2 == 1) { return ((res * res) % mod * a) % mod; } else return (res * res) % mod; } void solve() { ll n, k; cin >> n >> k; vector<ll>v(n+1); for (ll i = 1; i <= n; i++)cin >> v[i]; vector<vector<ll>>dp(n + 1 , vector<ll>(k + 1,1e18)); dp[0][0] = 0; for (ll i = 1; i <= n; i++) { for (ll j = 1; j <= k; j++) { ll mx = 0; for (ll i1 = i; i1 >= j; i1--) { mx = max(mx, v[i1]); dp[i][j] = min(dp[i][j], dp[i1 - 1][j - 1] + mx); } } } cout << dp[n][k] << endl; } signed main() { ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr); ll t = 1; //cin >> t; while (t--) { solve(); } }