program skill;
const MAX=255;
var n,m,i,j,k:integer;
  A,P,S:array[-1..50,-1..50]of longint;
  F:array[-1..50,-1..50,-1..50]of longint;
procedure GMax(var x:longint;y:longint);
begin
  if x<y then x:=y;
end;
begin
  assign(input,'skill.in'); reset(input);
  assign(output,'skill.out'); rewrite(output);
  readln(n,m);
  fillchar(S,sizeof(S),0); fillchar(P,sizeof(P),0);
  for i:=1 to n do
    for j:=1 to n+1-i do
    begin
      read(A[i,j]);
      P[i,j]:=(i+1) div 2;
      S[i,j]:=S[i-2,j+1]+A[i,j];
    end;
  fillchar(F,sizeof(F),255);
  F[1,1,1]:=A[1,1];
  F[0,1,0]:=0;
  for j:=1 to n do
    for i:=0 to n-j+1 do
      for k:=0 to m do
        if F[i,j,k]<>-1 then
        begin
          GMax( F[i+1,j,k+P[i+1,j]] , F[i,j,k]+S[i+1,j] );
          if i=0 then GMax( F[i,j+1,k] , F[i,j,k] );
          GMax( F[i-1,j+1,k+P[i-1,j+1]] , F[i,j,k]+S[i-1,j+1] );
        end;
  writeln(F[0,n+1,m]);
  close(input); close(output);
end.