#include<iostream> #include<vector> #include<algorithm> #include<string> #include<cmath> #include<set> #include<map> #include<queue> #include<stack> #include<unordered_map> #include<unordered_set> using namespace std; using ll = long long; ll mod = 1e9 + 7; ll gcd(ll a, ll b) { if (b == 0)return a; else return gcd(b, a % b); } void solve() { ll n, k; cin >> n >> k; vector<ll>v(n + 1); for (ll i = 1; i <= n; i++) { cin >> v[i]; } stack<pair<ll, ll>>st; vector<ll>mec(n + 1, 0); for (ll i = 1; i <= n; i++) { while (st.size() && st.top().first < v[i]) { st.pop(); } if (st.size()) { mec[i] = st.top().second; } st.push({ v[i],i }); } //for (ll i = 1; i <= n; i++)cout << mec[i] << " "; //cout << endl; vector<vector<vector<ll>>>dp(n + 1, vector<vector<ll>>(k + 1, vector<ll>(2, 1e18))); dp[0][0][0] = 0; dp[0][0][1] = 0; for (ll i = 1; i <= n; i++) { for (ll j = 1; j <= k; j++) { ll urde = mec[i]; dp[i][j][1] = min(dp[i][j][1], dp[max(j - 1, urde)][j - 1][1] + v[i]); dp[i][j][1] = min(dp[i][j][1], dp[max(j - 1, urde)][j - 1][0] + v[i]); dp[i][j][0] = min(dp[i][j][0], dp[urde][j][1]); dp[i][j][0] = min(dp[i][j][0], dp[urde][j][0]); } } cout << min(dp[n][k][0], dp[n][k][1]) << endl; } signed main() { ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr); ll t = 1; //cin >> t; while (t--) { solve(); } }