记录编号	20423	评测结果	AAAAAAAAAA
题目名称	逛街	最终得分	100
用户昵称	Achilles	是否通过	通过
代码语言	Pascal	运行时间	0.151 s
提交时间	2010-10-26 07:54:22	内存使用	1.74 MiB

program shop;
var
  ans,n,x,y,i,j,top,topt,now,last:longint;
  sz:array[0..300,1..4]of longint;
  tab:array[0..1,0..1000,0..100]of longint;
  cut:array[1..100000,1..2]of longint;
  hx:array[0..1000,0..100]of boolean;
begin
  assign(input,'shop.in');
  assign(output,'shop.out');
  reset(input);
  rewrite(output);
  readln(n,x,y);
  for i:=1 to n do
    readln(sz[i,1],sz[i,2],sz[i,3],sz[i,4]);
  top:=1;
  cut[1,1]:=0;
  cut[1,2]:=0;
  fillchar(tab,sizeof(tab),0);
  now:=0;
  last:=1;
  fillchar(hx,sizeof(hx),true);
  for i:=1 to n do
  begin
    topt:=top;
    for j:=1 to top do
    begin
      if (cut[j,1]+sz[i,1]<=x)and(cut[j,2]+sz[i,2]<=y) then begin
        if tab[last,cut[j,1],cut[j,2]]+sz[i,3]>tab[now,cut[j,1]+sz[i,1],cut[j,2]+sz[i,2]] then begin
          tab[now,cut[j,1]+sz[i,1],cut[j,2]+sz[i,2]]:=tab[last,cut[j,1],cut[j,2]]+sz[i,3];
          if hx[cut[j,1]+sz[i,1],cut[j,2]+sz[i,2]] then begin
            topt:=topt+1;
            cut[topt,1]:=cut[j,1]+sz[i,1];
            cut[topt,2]:=cut[j,2]+sz[i,2];
            hx[cut[j,1]+sz[i,1],cut[j,2]+sz[i,2]]:=false;
          end;
        end;
      end;
      if (cut[j,1]+sz[i,1]*sz[i,4]<=x)and(cut[j,2]+sz[i,2]*sz[i,4]<=y) then begin
        if tab[last,cut[j,1],cut[j,2]]+sz[i,3]*sz[i,4]>tab[now,cut[j,1]+sz[i,1]*sz[i,4],cut[j,2]+sz[i,2]*sz[i,4]] then begin
          tab[now,cut[j,1]+sz[i,1]*sz[i,4],cut[j,2]+sz[i,2]*sz[i,4]]:=tab[last,cut[j,1],cut[j,2]]+sz[i,3]*sz[i,4];
          if hx[cut[j,1]+sz[i,1]*sz[i,4],cut[j,2]+sz[i,2]*sz[i,4]] then begin
            topt:=topt+1;
            cut[topt,1]:=cut[j,1]+sz[i,1]*sz[i,4];
            cut[topt,2]:=cut[j,2]+sz[i,2]*sz[i,4];
            hx[cut[j,1]+sz[i,1]*sz[i,4],cut[j,2]+sz[i,2]*sz[i,4]]:=false;
          end;
        end;
      end;
    end;
    for j:=1 to top do
      if tab[last,cut[j,1],cut[j,2]]>tab[now,cut[j,1],cut[j,2]] then tab[now,cut[j,1],cut[j,2]]:=tab[last,cut[j,1],cut[j,2]];
    top:=topt;
    now:=(now+1)mod 2;
    last:=(last+1)mod 2;
  end;
  ans:=0;
  for i:=1 to top do
    if tab[last,cut[i,1],cut[i,2]]>ans then ans:=tab[last,cut[i,1],cut[i,2]];
  writeln(ans);
  close(input);
  close(output);
end.