#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
int const maxn = 10000; int const maxk = 1000;
int A[1+maxk][1+maxn], S[1+maxn], V[1+maxn], N, K;

void dp()
{ int q, i, u;
  for ( q=2; K>=q; ++q)
  {
    A[q][q]=S[q];
    u=max(A[q-1][q-1]-S[q-1],A[q-1][q]-S[q]);
    for (i=q+1; N>=i; ++i)
    {
      A[q][i] = max(A[q][i-1], S[i]+u);
      u = max(u, A[q-1][i]-S[i]);
    }
  }
}

void init1()
{ int i, u;
  u=A[1][1]=V[1];
  for(i=2; N>=i; ++i) { u=max(u+V[i],V[i]); A[1][i]=max(A[1][i-1],u); } 
}

void init2()
{ int i;
  A[1][1]=S[1];
  for(i=2; N>=i; ++i) { A[1][i]=max(A[1][i],S[i]); }
}

int maxval1()
{ int i, u=A[K][K];
  for (i=K+1; N>=i; ++i) { u=max(u,A[K][i]); }
  return u;
}

int maxval2()
{ int i, u=A[K][N], w=0;
  for (i=N-1; K<=i; --i) { w=max(w,S[N]-S[i]); u=max(u,A[K][i]+w); }
  return u;
}

int main()
{
  ifstream is("ferma.in"); ofstream os("ferma.out");
  is >> N >> K; int i, s;
  for (i=1, S[0]=0; N>=i; ++i) { is >> V[i]; S[i]=S[i-1]+V[i]; }
  if (N>=K)
  { init1(); dp(); s=maxval1(); init2(); dp(); s=max(s,maxval2()); s=max(0,s); }
  else { s=0; }
  os << s << endl;
}