记录编号	21879	评测结果	AAAAAAAAAA
题目名称	技能树	最终得分	100
用户昵称	maxiem	是否通过	通过
代码语言	Pascal	运行时间	0.183 s
提交时间	2010-11-15 18:07:43	内存使用	9.11 MiB

program skill;
var
  f:array [0..51,0..51,0..500] of longint;
  ans,tmp,n,m,i,j,a,k:longint;
  table,t,c,s:array [0..500,0..500] of longint;
begin
  assign (input,'skill.in');
  reset (input);
  readln (n,m);
  fillchar (c,sizeof(c),0);
  fillchar (s,sizeof(s),0);
  fillchar (t,sizeof(t),0);
  for i:=1 to n do begin;
    for j:=1 to n-i+1 do begin
	  read (table[i,j]);
	  s[i,j]:=s[i-1,j]+table[i,j];
	  c[i,j]:=c[i-1,j]+1;
	end;
	readln;
  end;
  fillchar (f,sizeof(f),0);
  for i:=1 to n do f[i,1,i]:=s[i,1];
  t[1,1]:=table[1,1];
  close (input);
  assign (output,'skill.out');
  rewrite (output);
  for j:=2 to n do begin
    for k:=0 to m do t[j,k]:=t[j-1,k];
	for i:=1 to n-j+1 do begin
	  a:=c[i,j];
	  for k:=a to m do begin
	    tmp:=f[i+1,j-1,k-a]+s[i,j];
     	if (i>1) then if tmp<f[i-1,j,k-1]+table[i,j] then tmp:=f[i-1,j,k-1]+table[i,j];
	if (i=1) then if tmp<t[j-1,k-1]+table[i,j] then tmp:=t[j-1,k-1]+table[i,j];
        f[i,j,k]:=tmp;
        if (i=1) then if t[j,k]<f[i,j,k] then t[j,k]:=f[i,j,k];
	  end;
	end;
  end;
  ans:=0;
  for i:=1 to n do if f[1,i,m]>ans then ans:=f[1,i,m];
  writeln (ans);
  close (output);
end.