/*huypheu 5 4 1 2 3 4 5 */ #include <bits/stdc++.h> #define int long long #define oo (LLONG_MAX/2) using namespace std; bool pok[100007]; int a[100007],f[100007][107]; signed main() { int n,k; cin >> n >> k; for(int i=1;i<=n;i++) { cin >> a[i]; } for(int i=1;i<=n;i++) { for(int j=1;j<=k;j++) { f[i][j]=oo; } } f[0][0]=0; stack <int> st; for(int i=n;i>=1;i--) { while(!st.empty() && a[st.top()]<=a[i]) st.pop(); if(st.empty()) pok[i]=1; st.push(i); } for(int j=1;j<=k;j++) { while(!st.empty()) st.pop(); for(int i=1+j-1;i<=n;i++) { f[i][j]=f[i-1][j-1]; } // cout << "concak" << endl; // for(int i=1;i<=n;i++) cout << f[i][j-1] << " "; // cout << endl; for(int i=1;i<=n;i++) { while(!st.empty() && a[st.top()]<=a[i]) { f[i][j]=min(f[i][j],f[st.top()][j]); st.pop(); } // if(st.empty()) f[i][j]=min(f[i][j],f[0][j]); st.push(i); } for(int i=1;i<=n;i++) { f[i][j]=f[i][j]+a[i]; } } int mi=oo; // for(int i=1;i<=n;i++) cout << pok[i] << " " ; // cout << endl; // for(int j=1;j<=k;j++) // { // for(int i=1;i<=n;i++) // { // cout << f[i][j] << " "; // } // cout << endl; // } for(int i=1;i<=n;i++) { if(pok[i]) mi=min(mi,f[i][k]); } cout << mi << endl; return 0; }