#include <cstdio>
#define MAXN 10000
#define MAXK 1000
int sp[MAXN+1];
int dp[MAXK+1][MAXN+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;
    }
    ans=0;
    for(j=1;j<=k;j++){
      best=dp[j-1][j-1]-sp[j-1];
      for(i=j;i<=n;i++){
        dp[j][i]=getmax(dp[j][i-1],best+sp[i]);
        if(dp[j-1][i]-sp[i]>best)
         best=dp[j-1][i]-sp[i];
      }
    }
    ans=getmax(dp[k][n],ans);
    dp[1][1]=sp[1];
    for(i=2;i<=n;i++)
       dp[1][i]=getmax(sp[i],dp[1][i-1]);
    for(j=2;j<=k;j++){
        best=dp[j-1][j-1]-sp[j-1];
        for(i=j;i<=n;i++){
            dp[j][i]=getmax(dp[j][i-1],best+sp[i]);
            if(dp[j-1][i]-sp[i]>best)
              best=dp[j-1][i]-sp[i];
        }
    }
    for(i=k;i<=n;i++)
      ans=getmax(ans,dp[k][i]+sp[n]-sp[i]);
    fprintf(fout,"%d" ,ans);
    fclose(fi);
    fclose(fout);
    return 0;
}