A tricky problem, similar to BFS brute force, but not quite the same because the condition is that all teachers must have someone.
So we use state compression DP to record, and each time we update, we need to sort, increasing the state from the current state with the most teachers.
Because if we update from the smallest teacher, it may update to a larger one, and after updating to a larger one, the larger one will update again.
This means one teacher is used twice.
//====================================================================||
// Name : Headmaster's Headache.cpp ||
// Date : May 30, 2013 11:44:48 AM ||
// Author : GCA ||
// 6AE7EE02212D47DAD26C32C0FE829006 ||
//====================================================================||
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <climits>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <cctype>
#include <utility>
using namespace std;
#ifdef ONLINE\_JUDGE
#define ll "%lld"
#else
#define ll "%I64d"
#endif
typedef unsigned int uint;
typedef long long int Int;
#define Set(a,s) memset(a,s,sizeof(a))
#define Write(w) freopen(w,"w",stdout)
#define Read(r) freopen(r,"r",stdin)
#define Pln() printf("\\n")
#define I\_de(x,n)for(int i=0;i<n;i++)printf("%d ",x\[i\]);Pln()
#define De(x)printf(#x"%d\\n",x)
#define For(i,x)for(int i=0;i<x;i++)
#define CON(x,y) x##y
#define Pmz(dp,nx,ny)for(int hty=0;hty<ny;hty++){for(int htx=0;htx<nx;htx++){\\
printf("%d ",dp\[htx\]\[hty\]);}Pln();}
#define M 10011
#define PII pair<int,int\>
#define PB push\_back
#define oo INT\_MAX
#define Set\_oo 0x3f
#define Is\_debug true
#define debug(...) if(Is\_debug)printf("DEBUG: "),printf(\_\_VA\_ARGS\_\_)
#define FOR(it,c) for(\_\_typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define eps 1e-6
bool xdy(double x,double y){return x>y+eps;}
bool xddy(double x,double y){return x>y-eps;}
bool xcy(double x,double y){return x<y-eps;}
bool xcdy(double x,double y){return x<y+eps;}
int min3(int x,int y,int z){
int tmp=min(x,y);
return min(tmp,z);
}
int max3(int x,int y,int z){
int tmp=max(x,y);
return max(tmp,z);
}
int s,m,n;
struct app{
vector<int\> teach;
int cost;
}apps\[105\];
int dp\[1<<20\];
int vis\[1<<20\];
bool cmp(int a,int b){
return a>b;
}
int main() {
ios\_base::sync\_with\_stdio(0);
while(~scanf("%d%d%d",&s,&m,&n)&&s+m+n){
for(int i=0;i<=(1<<(s\*2));i++)dp\[i\]=oo;
memset(vis,0,sizeof(vis));
int nowcost=0;
int allcost=0;
int sub;
int alrsub=0;
for(int i=0;i<m;i++){
scanf("%d",&nowcost);
allcost+=nowcost;
for(;;){
scanf("%d",&sub);
int tmp=1<<(sub\*2-1);
if((1&(alrsub>>(sub\*2-1)))){
tmp>>=1;
}
alrsub|=tmp;
if(getchar()=='\\n')break;
}
}
for(int i=0;i<n;i++){
int cost;
scanf("%d",&cost);
apps\[i\].cost=cost;
apps\[i\].teach.clear();
for(;;){
scanf("%d",&sub);
apps\[i\].teach.PB(sub);
if(getchar()=='\\n')break;
// printf("%d\\n",apps\[i\].cost);
}
}
vector<int\> q;
q.PB(alrsub);
dp\[alrsub\]=allcost;
vis\[alrsub\]=1;
for(int i=0;i<n;i++){
sort(q.begin(),q.end(),cmp);
int size=q.size();
for(int j=0;j<size;j++){
int tmp=q\[j\];
int nc=apps\[i\].cost;
FOR(it,apps\[i\].teach){
int sub=(\*it);
int nt=1<<(sub\*2-1);
if(1&(tmp>>(sub\*2-1))){
nt>>=1;
}
tmp|=nt;
}
if(dp\[q\[j\]\]+nc<dp\[tmp\]){
dp\[tmp\]=dp\[q\[j\]\]+nc;
if(!vis\[tmp\]){
q.PB(tmp);
vis\[tmp\]=1;
}
}
}
}
printf("%d\\n",dp\[((1<<(s\*2))-1)\]);
}
}