#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 s)
{ int i, q, u;
  for (q=s; K>=q; ++q)
  for (i=1, u=0; N>=i; ++i)
  { A[q][i] = max(A[q-1][i], S[i]+u); u = max(u, A[q-1][i]-S[i]); }
}

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