记录编号	21768	评测结果	AAAAAAAAAA
题目名称	技能树	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	Pascal	运行时间	0.285 s
提交时间	2010-11-15 12:44:58	内存使用	6.59 MiB

program skill;
var k,i,j,n,m:longint;
  cost,sum,A:array[-1..51,-1..51]of longint;
  F:array[0..601,-1..51,-1..51]of longint;
begin
  assign(input,'skill.in'); reset(input);
  assign(output,'skill.out'); rewrite(output);
  readln(n,m);
  fillchar(sum,sizeof(sum),0);
  for i:=1 to n do
    for j:=1 to n+1-i do
    begin
      read(A[i,j]);
      sum[i,j]:=sum[i-2,j+1]+A[i,j];
      cost[i,j]:=(i+1)div 2;
    end;
  fillchar(F,sizeof(F),255);
  F[0,0,1]:=0;
  F[1,1,1]:=A[1,1];
  for j:=1 to n do
    for i:=0 to n+1-j do
      for k:=0 to m do
      if F[k,i,j]<>-1 then
      begin
        if F[k+cost[i+1,j],i+1,j]<F[k,i,j]+sum[i+1,j] then
          F[k+cost[i+1,j],i+1,j]:=F[k,i,j]+sum[i+1,j];
        if (i=0)and(F[k,i,j+1]<F[k,i,j]) then
          F[k,i,j+1]:=F[k,i,j];
        if F[k+cost[i-1,j+1],i-1,j+1]<F[k,i,j]+sum[i-1,j+1] then
          F[k+cost[i-1,j+1],i-1,j+1]:=F[k,i,j]+sum[i-1,j+1];
      end;
  writeln(F[m,0,n+1]);
  close(input);close(output);
end.