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

var
a,s:array[0..51,0..51]of longint;
n,m,i,j,k,x:longint;
f:array[0..51,0..51,0..501]of longint;
y:array[0..51,0..51,0..501]of boolean;

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

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

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

dp:=f[u,b,l];exit;
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:=i to n do
    read(a[j,i]);
for i:=1 to  n do
  for j:=1 to  i do
    s[i,j]:=s[i,j-1]+a[i,j];

x:=dp(1,1,m);

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