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

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

int n,k,mn,a[10005],s[10005],dp[10005][2],mx[10005][2],last[10005][2],lastmx[10005][2],st[10005],dr[10005],sol=-2147000000;
void CalcSums()
{ int i,sum;
    sum=0;
   for(i=1;i<=n;i++)
   { sum+=a[i];
     if (i==1) st[i]=sum;
      else st[i]=max(st[i-1],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);


   }
}
int main()
{ int i,j,t,x,y,l1,l2,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;
      last[i][l2]=ind;


      if (i>1 && dp[i-1][l2]>dp[i][l2])
        {dp[i][l2]=dp[i-1][l2];
         last[i][l2]=last[i-1][l2]; }

      if (i==1)
        {mx[i][l2]=dp[i][l2]-s[i];
         lastmx[i][l2]=last[i][l2];
        }
       else
        { if (dp[i][l2]-s[i]>mx[i-1][l2])
            {mx[i][l2]=dp[i][l2]-s[i];
             lastmx[i][l2]=last[i][l2];
            }
           else
            { mx[i][l2]=mx[i-1][l2];
              lastmx[i][l2]=lastmx[i-1][l2];
            }

        }

       if (s[i]<=mn) {ind=i+1; mn=s[i];}
     }



   for(j=2;j<=k;j++)
   { l1^=1; l2^=1;

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

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

       if (i>j)
        {

          if (dp[i-1][l2]>dp[i][l2])
           { last[i][l2]=last[i-1][l2];
             dp[i][l2]=dp[i-1][l2];
           }

        }
       if (i==j)
         {mx[i][l2]=dp[i][l2]-s[i];
          lastmx[i][l2]=last[i][l2];
         }
        else
        { if (dp[i][l2]-s[i]>mx[i-1][l2])
          { mx[i][l2]=dp[i][l2]-s[i];
            lastmx[i][l2]=last[i][l2];
          }
          else
          { mx[i][l2]=mx[i-1][l2];
            lastmx[i][l2]=lastmx[i-1][l2];
          }
        }
     }
   }

     CalcSums();

 for(i=1;i<=n;i++)
  { x=last[i][l1];
    y=i;
   // cout<<i<<" "<<st[x-1]<<" "<<dr[y+1]<<"\n";
    if (x>1 && y<n) sol=max(sol,dp[i][l1]+st[x-1]+dr[y+1]);
    if (i>=k) sol=max(sol,dp[i][l2]);
  }


   g<<sol;
    return 0;
}