记录编号	8167	评测结果	AAAAAAAAAA
题目名称	[BYVoid S1] 灵魂分流药剂	最终得分	100
用户昵称	lc	是否通过	通过
代码语言	Pascal	运行时间	0.032 s
提交时间	2008-11-13 11:41:18	内存使用	0.11 MiB

program soultap;
 var
    n,m,a,b,ans:longint;
    start,last:array[1..100] of longint;
    w,v,t,p:array[1..100] of longint;

procedure swap(var a,b:longint);
 var
    temp:longint;
 begin
 temp:=a; a:=b; b:=temp
 end;


procedure init;
 var
    i,j,k:longint;

 begin
  readln(n,m,A,B);
  for i:=1 to n do
  read(w[i],v[i],t[i],p[i]);
  for i:=1 to n-1 do
   for j:=i+1 to n do
   if t[i]>t[j]
      then begin
           swap(w[i],w[j]);
           swap(v[i],v[j]);
           swap(t[i],t[j]);
           swap(p[i],p[j]);
           end;
  i:=1; start[1]:=1; k:=1;
  While i<=n do  begin
   inc(i);
   if t[i]<>t[i-1]
      then begin
           last[k]:=i-1;
           inc(k);
           start[k]:=i
           end;
    end;
  inc(k); last[k]:=n;
 end;



procedure search(k:integer; ww,vv,pp:longint);
 var
    i:integer;
 begin
   if (ww>A) or (vv>B) then exit;
   if pp>ans then ans:=pp;
   if k>m then exit;
   for i:=start[k] to last[k] do
   search(k+1,ww+w[i],vv+v[i],pp+p[i]);
   search(k+1,ww,vv,pp);
 end;



begin
  assign(input,'soultap.in');
  assign(output,'soultap.out');
  reset(input); rewrite(output);
  init;
  ans:=0;
  search(1,0,0,0);
  writeln(ans);
  close(input); close(output);
end.