#include <iostream>
#include <fstream>
#include <cstring>
#define inf 0x3f3f3f

using namespace std;
ifstream f("ferma.in");
ofstream g("ferma.out");

int n,mn,l1,l2,a[10005],s[10005],dp[10005][2],mx[10005][2],dr[10005],sol=-2147000000;

void CalcSums()
{ int i,sum;
    sum=0;
   for(i=n;i>=1;i--)
   { sum+=a[i];

     if (i==n) dr[i]=sum;
      else dr[i]=max(dr[i+1],sum);
   }
}

void Dinamica(int k)
{ int i,j;
  for(j=2;j<=k;j++)
   { l1^=1; l2^=1;

     for(i=1;i<=n;i++)
      {dp[i][l2]=0;
       mx[i][l2]=0;
      }

     for(i=j;i<=n;i++)
     { dp[i][l2]=s[i]+mx[i-1][l1];


       if (i>j)
         dp[i][l2]=max(dp[i][l2],dp[i-1][l2]);

       if (i==j)
         mx[i][l2]=dp[i][l2]-s[i];
        else
         mx[i][l2]=max(mx[i-1][l2],dp[i][l2]-s[i]);
     }
   }
}
int main()
{ int i,j,k,ind=1;
    f>>n>>k;
     mn=0;
     memset(dp,inf,sizeof(inf));
      l1=0; l2=1;

    for(i=1;i<=n;i++)
     {f>>a[i];
      s[i]=s[i-1]+a[i];

      dp[i][l2]=s[i]-mn;

     if (i>1) dp[i][l2]=max(dp[i][l2],dp[i-1][l2]);

      if (i==1)
        mx[i][l2]=dp[i][l2]-s[i];
        else
         mx[i][l2]=max(dp[i][l2]-s[i],mx[i-1][l2]);

       if (s[i]<=mn) mn=s[i];
     }

  CalcSums();
  Dinamica(k);

 for(i=k;i<=n;i++)
  sol=max(sol,dp[i][l2]);

  l1=0; l2=1;
 for(i=1;i<=n;i++)
 { dp[i][l2]=s[i];
   if (i>1) dp[i][l2]=max(dp[i][l2],dp[i-1][l2]);
   if (i==1) mx[i][l2]=dp[i][l2]-s[i];
    else mx[i][l2]=max(mx[i][l2],mx[i-1][l2]);
 }

  Dinamica(k);
   //cout<<dp[4][1];
 //for(i=k;i<n;i++)
 // sol=max(sol,dp[i][l2]+dr[i+1]);
   g<<sol;
    return 0;
}