program skill(input,output);

var
  n,m,ans,i,j:longint;
  t:array[1..50,1..50]of longint;
  sum:array[0..50,0..50]of longint;
  tx:array[0..50]of longint;

function go(const deep,height,s,yellow:longint):boolean;
  var
    i,h:longint;
  begin
    if (yellow<0)or(s+tx[deep]<ans) then
      exit(true);

    if deep<n then
    begin
      if height=0 then
        h:=0
      else
        h:=height-1;

      for i:=h to n-deep do
        if go(deep+1,i,s+sum[deep+1,i],yellow-i) then
          break
    end
    else if s>ans then
      ans:=s;

    exit(false);
  end;

begin
  assign(input,'skill.in');
  reset(input);
  assign(output,'skill.out');
  rewrite(output);

  readln(n,m);
  for i:=1 to n do
    for j:=1 to n-i+1 do
    begin
      read(t[i,j]);
      sum[j,i]:=sum[j,i-1]+t[i,j];
    end;

  for i:=n downto 0 do
    tx[i]:=tx[i+1]+sum[i+1,n-i];

  for i:=0 to n do
    if go(1,i,sum[1,i],m-i) then
      break;

  writeln(ans);

  close(input);
  close(output);
end.