#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;

const int nmax = 100005; const int kmax = 105;

int N,k,a[nmax],b[nmax],dp[nmax][2],aint[nmax][2];
stack<int> s;

inline void Precalc(){
 int i;

    for(i = N; i; --i){
            while(!s.empty() && a[i] > a[s.top()]){
                b[s.top()] = i;
                s.pop();
           }
        s.push(i);
    }
}

inline void Update(int nod,int st,int dr,int poz,int j,int val){

  if(st == dr && st == poz){

    aint[nod][j] = val;
    return;
  }

  int mij = (st + dr)/2;

    if(mij >= poz)
        Update(2*nod,st,mij,poz,j,val);
    else
        Update(2*nod+1,mij+1,dr,poz,j,val);

  aint[nod][j] = min(aint[2*nod][j],aint[2*nod+1][j]);
  //if(poz == 2 && j == 1 && val == 5) cout << nod <<' ';
}

inline int Query(int nod,int st,int dr,int l,int r,int j){


 if(st == l && dr == r){
        //if(l == 2 && r == 2 && j == 1) cout << nod <<' ';
    return aint[nod][j];
 }

 int mij = (st+dr)/2;

 if(mij < l)
    return Query(2*nod+1,mij+1,dr,l,r,j);
 else if(mij >= r)
    return Query(2*nod,st,mij,l,r,j);
 else{

    int x = Query(2*nod,st,mij,l,mij,j);
    int y = Query(2*nod+1,mij+1,dr,mij+1,r,j);


    return min(x,y);
 }
}
inline void Ksecv(){
 int i,j,sum,xi,u,p;

 memset(dp,INF,sizeof(dp));
 memset(aint,INF,sizeof(aint));

 dp[1][0] = p = a[1];
 u = 1;
    Update(1,1,N,1,0,a[1]);

  for(i = 2; i <= N; ++i,u^=1){
        p = max(p,a[i]);

    for(j = 1; j <= k; ++j){

         if(j > i)break;

    if(j == 1) {dp[i][u] = p;Update(1,1,N,1,u,p);continue;}

    xi = b[i];
     if(!b[i]) ++xi;

        sum = Query(1,1,N,xi,i-1,u^1);


                dp[i][u] = min(dp[b[i]][u],a[i]+sum);
             if(i == 3 && j == 2) cout << sum <<' ';
   // cout << i <<' '<<dp[i][u]<<'\n';
        Update(1,1,N,i,u,dp[i][u]);
       // if(i == 2 && j == 2) cout << dp[i][u];
  }
  }
}
int main(){
    int i;
    freopen ("ksecv.in","r",stdin);
    freopen ("ksecv.out","w",stdout);

    scanf("%d %d\n",&N,&k);
    for(i = 1; i <= N; ++i) scanf("%d ",&a[i]);

    Precalc();
    Ksecv();

    //printf("%d\n",dp[N][0]);
    return 0;
}