记录编号	21826	评测结果	AAAAAAAAAA
题目名称	500.技能树	最终得分	100
用户昵称	belong.zmx	是否通过	通过
代码语言	Pascal	运行时间	0.274 s
提交时间	2010-11-15 16:50:16	内存使用	6.35 MiB

program skill(input,output);
var
 a,s:array[0..50,0..50]of longint;
 f:array[0..50,0..50,0..500]of longint;
 g:array[0..50,0..50,0..500]of boolean;
 m,n:longint;
 i,j,k:longint;

function min(a,b:longint):longint;
begin
 if a>b then min:=b else min:=a;
end;

function max(a,b:longint):longint;
begin
 if a>b then max:=a else max:=b;
end;

function dp(x,y,z:longint):longint;
var
 i,t:longint;
begin
 if (x>n)or(z<=0) then exit(0);
 if (g[x,y,z]=true) then exit(f[x,y,z]);
 g[x,y,z]:=true;
 t:=min(y,z);
 for i:=0 to t do
  f[x,y,z]:=max(f[x,y,z],s[x,i]+dp(x+1,i+1,z-i));
 exit(f[x,y,z]);
end;

begin
 assign(input,'skill.in');
 reset(input);
 readln(n,m);
 for i:=1 to n do
 begin
  for j:=i to n do read(a[j,i]);
  readln;
 end;
 close(input);

 for i:=1 to n do
  for j:=1 to i do
   s[i,j]:=s[i,j-1]+a[i,j];

 assign(output,'skill.out');
 rewrite(output);
 writeln(dp(1,1,m));
 close(output);
end.