program skill;
var
  cost,sum,map:array[-1..51,-1..51]of longint;
  tab:array[-1..51,-1..51,-1..601]of longint;
  n,m,i,j,k:longint;
begin
  assign(input,'skill.in');
  assign(output,'skill.out');
  reset(input);
  rewrite(output);
  readln(n,m);
  for i:=-1 to 51 do
    for j:=-1 to 51 do
      for k:=-1 to 601 do
        tab[i,j,k]:=-1;
  for i:=1 to n do
  begin
    for j:=1 to n+1-i do
      read(map[i,j]);
    readln;
  end;
  for i:=1 to n do
    for j:=1 to n+1-i do
    begin
      sum[i,j]:=sum[i-2,j+1]+map[i,j];
      cost[i,j]:=(i+1) div 2;
    end;
  tab[0,0,1]:=0;
  tab[1,1,1]:=map[1,1];
  for j:=1 to n do
    for i:=0 to n+1-j do
      for k:=0 to m do
        if tab[i,j,k]<>-1 then
        begin
          if tab[i+1,j,k+cost[i+1,j]]<tab[i,j,k]+sum[i+1,j] then
            tab[i+1,j,k+cost[i+1,j]]:=tab[i,j,k]+sum[i+1,j];
          if (i=0)and(tab[i,j+1,k]<tab[i,j,k]) then
            tab[i,j+1,k]:=tab[i,j,k];
          if tab[i-1,j+1,k+cost[i-1,j+1]]<tab[i,j,k]+sum[i-1,j+1] then
            tab[i-1,j+1,k+cost[i-1,j+1]]:=tab[i,j,k]+sum[i-1,j+1];
        end;
  writeln(tab[0,n+1,m]);
  close(input);
  close(output);
end.