#include <cstdio>
#include <algorithm>
#define MAXN 10000
#define MAXK 1000
int sp[MAXN+1];
int dp[MAXK+1][MAXN+1];
 main(){
    FILE*fin ,*fout;
    int i,j,n,k,x,best,ans;
    fin = fopen("ferma.in" ,"r");
    fout = fopen("ferma.out" ,"w");
    fscanf(fin ,"%d %d " ,&n,&k);
    for(i=1;i<=n;i++){
      fscanf(fin ,"%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]=std::max(dp[j][i-1],best+sp[i]);
        if(dp[j-1][i]-sp[i]>best)
         best=dp[j-1][i]-sp[i];
      }
    }
    ans=std::max(dp[k][n],ans);
    dp[1][1]=sp[1];
    for(i=2;i<=n;i++)
       dp[1][i]=std::max(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]=std::max(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=std::max(ans,dp[k][i]+sp[n]-sp[i]);
    fprintf(fout,"%d" ,ans);
    fclose(fin );
    fclose(fout);
    return 0;
}