记录编号	49676	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	还是“金明的预算方案”	最终得分	100
用户昵称	digital-T	是否通过	通过
代码语言	Pascal	运行时间	0.799 s
提交时间	2012-11-08 20:30:22	内存使用	1.70 MiB

var
n,l,w,limit,i,j,www,a,b,s,ww:longint;
c,d,k,num,h:array[1..60]of longint;
t,tt:array[0..200000]of longint;
fc,fd:array[1..60,1..10]of longint;
begin
assign(input,'budgetb.in');reset(input);
assign(output,'budgetb.out');rewrite(output);
fillchar(t,sizeof(t),0);
fillchar(fc,sizeof(fc),0);
fillchar(fd,sizeof(fd),0);
fillchar(num,sizeof(num),0);
read(limit,n,s);
for l:=1 to n do
begin
read(c[l],d[l],k[l]);
 if k[l]>0 then
 begin
  inc(num[k[l]]);
  fc[k[l],num[k[l]]]:=c[l];
  fd[k[l],num[k[l]]]:=d[l];
  h[k[l]]:=h[k[l]]+c[l];
 end;
end;
//________________________________
for l:=1 to n do
 if k[l]=0 then
 for w:=limit-c[l] downto 0 do
  begin
   if(w=0)or(t[w]>0)then
    begin
     if t[w+c[l]]<t[w]+c[l]*d[l] then t[w+c[l]]:=t[w]+c[l]*d[l];

     if num[l]>0 then
      begin

       fillchar(tt,sizeof(tt),0);
       tt[w+c[l]]:=t[w]+c[l]*d[l];

       for ww:=1 to num[l] do
        begin
         //if limit<w+c[l]+h[l]-fc[l,ww]then i:=limit else i:=w+c[l]+h[l]-fc[l,ww];
          for www:=limit downto w+c[l] do
           if tt[www]>0 then
            begin
             if tt[www+fc[l,ww]]<tt[www]+fc[l,ww]*fd[l,ww]then
              tt[www+fc[l,ww]]:=tt[www]+fc[l,ww]*fd[l,ww];
            end;
        end;
       //if limit<w+c[l]+h[l] then i:=limit else i:=w+c[l]+h[l];
       for ww:=w+c[l]+1 to limit do if tt[ww]>t[ww] then t[ww]:=tt[ww];

      end;
    end;
  end;
//______________________________________________

//______________________________________________
l:=0;
for w:=limit downto 1 do if t[w]>t[l] then l:=w;
write(t[l]);
close(input);
close(output);
end.