program ferma;
  const
    fin='ferma.in';
    fout='ferma.out';
    nmax=10000;
    kmax=1000;
  var
    best:array[0..1,0..nmax] of longint;
    s:array[0..nmax] of longint;
    old,new:integer;
    i,j,k,x,y,max,n:longint;

function maxim(x,y:longint):longint;
  begin
    if x>y then
      maxim:=x
    else
      maxim:=y;
  end;

procedure init_best;
  begin
    fillchar(best,sizeof(best),0);
  end;

begin
  assign(input,fin);
    reset(input);
    readln(n,k);
    s[0]:=0;
    for i:=1 to n do
      begin
        read(x);
        s[i]:=s[i-1]+x;
      end;
    new:=1;old:=0;
    init_best;
    for i:=1 to k do
      begin
        old:=new;new:=old xor 1;
        max:=0;
        for j:=1 to n do
          begin
            if best[new,j-1]>max+s[j] then
              best[new,j]:=best[new,j-1]
            else
              best[new,j]:=max+s[j];
            if best[old,j]-s[j]>max then
              max:=best[old,j]-s[j];
          end;
      end;
    x:=best[new,n];
    init_best;
    for i:=1 to n do
      best[new,i]:=s[i];
    for i:=1 to k do
      begin
        old:=new;new:=old xor 1;
        max:=0;
        for j:=1 to n do
          begin
            if best[new,j-1]>max+s[j] then
              best[new,j]:=best[new,j-1]
            else
              best[new,j]:=max+s[j];
            if best[old,j]-s[j]>max then
              max:=best[old,j]-s[j];
          end;
      end;
    for i:=1 to n do
      if s[n]-s[i]+best[new,i]>x then
        x:=s[n]-s[i]+best[new,i];
  close(input);
  assign(output,fout);
    rewrite(output);
    writeln(x);
  close(output);
end.