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

program shop;
var
  data:array [1..300] of record
    w,v,t,h:longint;
  end;
  f:array [0..1,0..1000,0..100] of longint;
  cut:array [1..100000] of record
    x,y:longint;
  end;
  now,last,ct,max,value,a1,b1,a2,b2,top,i,j,n,x,y:longint;
begin
  fillchar (f,sizeof(f),0);
  fillchar (data,sizeof(data),0);
  fillchar (cut,sizeof(cut),0);
  assign (input,'shop.in');
  reset (input);
  readln (n,x,y);
  for i:=1 to n do with data[i] do readln (w,v,t,h);
  close (input);
  assign (output,'shop.out');
  rewrite (output);
  top:=1;cut[top].x:=0;cut[top].y:=0;
  f[0,0,0]:=0;now:=1;last:=0;
  for i:=1 to n do begin
    ct:=top;
    for j:=1 to top do begin
	  if f[now,cut[j].x,cut[j].y]<f[last,cut[j].x,cut[j].y] then f[now,cut[j].x,cut[j].y]:=f[last,cut[j].x,cut[j].y];
	  a1:=cut[j].x+data[i].w;b1:=cut[j].y+data[i].v;
	  a2:=cut[j].x+data[i].w*data[i].h;b2:=cut[j].y+data[i].v*data[i].h;
	  if (a1<=x) and (b1<=y) then begin
	    value:=f[last,cut[j].x,cut[j].y]+data[i].t;
            if value>f[now,a1,b1] then f[now,a1,b1]:=value;
            if f[last,a1,b1]=0 then begin
                  inc(ct);
		  cut[ct].x:=a1;cut[ct].y:=b1;
            end
	  end;
	  if (a2<=x) and (b2<=y) then begin
	    value:=f[last,cut[j].x,cut[j].y]+data[i].t*data[i].h;
            if value>f[now,a2,b2] then f[now,a2,b2]:=value;
            if f[last,a2,b2]=0 then begin
		  inc(ct);
		  cut[ct].x:=a2;cut[ct].y:=b2;
            end
          end;
	end;
        top:=ct;
		last:=(last+1) mod 2;
		now:=(now+1) mod 2;
  end;
  max:=0;
  for i:=1 to top do if max<f[0,cut[i].x,cut[i].y] then max:=f[0,cut[i].x,cut[i].y];
  writeln (max);
  close (output);
end.