#include <bits/stdc++.h> #define maxn 100010 #define maxk 110 #define FOR(i,a,b) for(int i=a;i<=b;++i) #define FORD(i,a,b) for(int i=a;i>=b;--i) typedef long long ll; using namespace std; const char *fi="BLOCKS.INP"; const char *fo="BLOCKS.OUT"; const int oo=1e9; int n,k,A[maxn],P[maxn],F[maxn][maxk]; stack<pair<int,int> > Q; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen(fi,"r",stdin); // freopen(fo,"w",stdout); cin>>n>>k; FOR(i,1,n) cin>>A[i]; P[0]=0; FOR(i,1,n) P[i]=max(P[i-1],A[i]); FOR(i,1,n) F[i][1]=P[i]; FOR(j,2,k){ F[0][j]=oo; while (!Q.empty()) Q.pop(); FOR(i,j,n){ int tmp = F[i-1][j-1]; while (!Q.empty() && A[Q.top().second]<=A[i]){ tmp = min(tmp,Q.top().first); Q.pop(); } F[i][j] = min(F[Q.empty()?0:Q.top().second][j], tmp+A[i]); Q.push({tmp,i}); } } cout<<F[n][k]; return 0; }