记录编号	24080	评测结果	AAAAAAAA
题目名称	软件补丁	最终得分	100
用户昵称	ybh	是否通过	通过
代码语言	Pascal	运行时间	0.076 s
提交时间	2011-03-28 10:27:39	内存使用	9.11 MiB

program bugs;
const
  maxv=1 shl 20-1;
var
  c0,c1,d0,d1,w:array[0..100] of longint;
  dist,q:array[0..maxv] of longint;
  b:array[0..maxv] of boolean;
  n,m,i,j,u,h,t,s:longint;  
  r:char;
  
begin
  assign(input,'bugs.in');
  reset(input);
  assign(output,'bugs.out');
  rewrite(output);
  
  readln(n,m);
  for i:=1 to m do
  begin
    read(w[i]);
    read(r);
    c1[i]:=0; c0[i]:=0;
    for j:=1 to n do
    begin
      read(r);
      if r='+' then c1[i]:=c1[i]+(1 shl (j-1));
      if r='-' then c0[i]:=c0[i]+(1 shl (j-1));
    end;
	read(r);
    d1[i]:=0; d0[i]:=0;
    for j:=1 to n do
    begin
      read(r);
      if r='+' then d1[i]:=d1[i]+(1 shl (j-1));
      if r='-' then d0[i]:=d0[i]+(1 shl (j-1));
    end;
	readln;
  end;
  
  h:=0;
  t:=1;
  s:=(1 shl n)-1;
  q[1]:=s;
  fillchar(b,sizeof(b),false);
  fillchar(dist,sizeof(dist),$FF);
  dist[s]:=0;
  b[s]:=true;
  while h<>t do
  begin
    h:=(h mod s)+1;
    i:=q[h];
    for u:=1 to m do
    begin
      if i or c1[u]<>i then continue;
      if (not i) or c0[u] <> (not i) then continue;
      j:=i and (not d0[u]);
      j:=j or d1[u];
      if (dist[i]+w[u]<dist[j]) or (dist[j]=-1) then 
      begin
        dist[j]:=dist[i]+w[u];
        if not b[j] then
        begin
          t:=(t mod s)+1;
          q[t]:=j;
          b[j]:=true;
        end;
      end;
    end;
    b[i]:=false;
  end;
  
  writeln(dist[0]);
  
  close(input);
  close(output);
end.