#include <cstdio>
#define MAXN 10000
#define MAXK 1000
#define INF 1000000000
int sp[MAXN+1];
int dp[MAXN+1][MAXK+1];
inline int getmax(int a,int b){
   if(a<b) return b;
   return a;
}
int main(){
    FILE*fi,*fout;
    int i,j,n,k,x,best,ans;
    fi=fopen("ferma.in" ,"r");
    fout=fopen("ferma.out" ,"w");
    fscanf(fi,"%d %d " ,&n,&k);
    for(i=1;i<=n;i++){
      fscanf(fi,"%d " ,&x);
      sp[i]=sp[i-1]+x;
    }
    for(i=1;i<=n;i++)
     for(j=1;j<=k;j++)
       dp[i][j]=-INF;
    for(j=1;j<=k;j++){
      dp[j][j]=sp[j];
      best=-INF;
      for(i=1;i<=j;i++)
       if(best<dp[i][j-1]-sp[i])
        best=dp[i][j-1]-sp[i];
      for(i=j+1;i<=n;i++){
        dp[i][j]=getmax(dp[i-1][j],best+sp[i]);
        if(dp[i][j-1]-sp[i]>best)
         best=dp[i][j-1]-sp[i];
      }
    }
    ans=dp[n][k];
    for(i=k;i<=n;i++)
      ans=getmax(ans,dp[i][k]+sp[n]-sp[i]);
    fprintf(fout,"%d" ,ans);
    fclose(fi);
    fclose(fout);
    return 0;
}