program ferma;
  const
    fin='ferma.in';
    fout='ferma.out';
    nmax=100;
    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
            best[new,j]:=maxim(best[new,j-1],max+s[j]);
            max:=maxim(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
            best[new,j]:=maxim(best[new,j-1],max+s[j]);
            max:=maxim(max,best[old,j]-s[j]);
          end;
      end;
    for i:=1 to n do
        x:=maxim(x,s[n]-s[i]+best[new,i]);
  close(input);
  assign(output,fout);
    rewrite(output);
    writeln(x);
  close(output);
end.