记录编号	22372	评测结果	AAAAAAAAAA
题目名称	情敌	最终得分	100
用户昵称	ybh	是否通过	通过
代码语言	Pascal	运行时间	1.068 s
提交时间	2010-11-18 19:53:45	内存使用	0.44 MiB

{情敌 NOIP模拟2010-11-18
 搜索 动态规划
 Author: yangbohua
 Time: 2010-11-18}
 
program rival;
var
  f:array[0..205,0..205] of int64;
  w,t:array[0..51] of longint;
  b:array[0..51] of boolean;
  tot:array[0..5] of longint;
  p:array[0..5,0..51] of longint;
  n,m,t1,t2,i,j,ww:longint;
  ans,sum:int64;

procedure dfs(step:longint);
var
  i,j,k:longint;
begin
  if step=m+1 then
  begin
    fillchar(f,sizeof(f),0);
    for i:=1 to n do
      if b[i] then
      begin
        for j:=t1 downto 0 do
          for k:=t2 downto 0 do
          begin
            if j-t[i]>=0 then
              if f[j-t[i],k]+w[i]>f[j,k]
                then f[j,k]:=f[j-t[i],k]+w[i];
            if k-t[i]*2>=0 then
              if f[j,k-t[i]*2]+w[i]>f[j,k]
                then f[j,k]:=f[j,k-t[i]*2]+w[i];
          end;
      end;
    if f[t1,t2]+ww>ans
      then ans:=f[t1,t2]+ww;
  end
  else
  begin
    if t1>=t[p[step,0]] then
    begin
      b[p[step,0]]:=false;
      t1:=t1-t[p[step,0]];
      ww:=ww+w[p[step,0]];
      dfs(step+1);
      ww:=ww-w[p[step,0]];
      t1:=t1+t[p[step,0]];
      b[p[step,0]]:=true;
    end;
    if t2>=t[p[step,0]]*2 then
    begin
      t2:=t2-t[p[step,0]]*2;
      b[p[step,0]]:=false;
      ww:=ww+w[p[step,0]];
      dfs(step+1);
      b[p[step,0]]:=true;
      ww:=ww-w[p[step,0]];
      t2:=t2+t[p[step,0]]*2;
    end;
    b[p[step,0]]:=false;
    for i:=1 to tot[step] do
      b[p[step,i]]:=false;
    dfs(step+1);
    for i:=1 to tot[step] do
      b[p[step,i]]:=true;
    b[p[step,0]]:=true;
  end;
end;

begin
  assign(input,'rival.in');
  reset(input);
  assign(output,'rival.out');
  rewrite(output);
  readln(t1,t2);
  readln(n,m);
  sum:=0;
  for i:=1 to n do
  begin
    readln(w[i],t[i]);
    sum:=sum+w[i];
  end;
  for i:=1 to m do
  begin
    read(p[i,0],tot[i]);
    for j:=1 to tot[i] do
      read(p[i,j]);
    readln;
  end;
  ww:=0;
  ans:=0;
  fillchar(b,sizeof(b),true);
  dfs(1);
  writeln(sum-ans);
  close(input);
  close(output);
end.