记录编号	21829	评测结果	AAAAAWWWEE
题目名称	500.技能树	最终得分	50
用户昵称	苏轼	是否通过	未通过
代码语言	Pascal	运行时间	0.037 s
提交时间	2010-11-15 16:52:23	内存使用	0.64 MiB

program skill(input,output);

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

function go(const l,h,y:longint):longint;
  var
    i,tmp,hh:longint;
  begin
    if h<0 then
      hh:=0
    else
      hh:=h;

    if mem[l,hh,y]<>0 then
      exit(mem[l,hh,y])
    else if ((y<0)or (y=0)and(h>0)) then
      mem[l,hh,y]:=-maxint
    else if y=0 then
      mem[l,hh,y]:=0
    else
    begin
      mem[l,hh,y]:=-maxint;
      for i:=hh to n-l+1 do
        if y-i>=0 then
        begin
          tmp:=go(l+1,i-1,y-i);
          if tmp+sum[l,i]>mem[l,hh,y] then
            mem[l,hh,y]:=tmp+sum[l,i]
        end
        else
          break;
    end;

    exit(mem[l,hh,y]);
  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;

  writeln(go(1,0,m));

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