#include <iostream>#include <cstdlib>#include <cstdio>#include <cstring>#include <algorithm>#include <queue>#include <map>#include <vector>#include <cstring>#define INT_INF 0x3fffffff#define LL_INF 0x3fffffffffffffff#define EPS 1e-12#define MOD 1000000007#define PI 3.141592653579798#define N 50005#define E 1000000using namespace std;typedef long long LL;typedef unsigned long long ULL;typedef double DB;struct Edge{ int en,cap,flow,next;} edge[E];int head[N] , tot , now[N];int source,sink,tot_num;int pre[N] , dis[N] , gap[N];void add_edge(int st,int en,int cap){ edge[tot].en=en; edge[tot].cap=cap; edge[tot].flow=0; edge[tot].next=head[st]; head[st]=tot++; edge[tot].en=st; edge[tot].cap=0; edge[tot].flow=0; edge[tot].next=head[en]; head[en]=tot++;}void augment(int flow){ for(int i=source;i!=sink;i=edge[now[i]].en) { edge[now[i]].flow+=flow; edge[now[i]^1].flow-=flow; }}int sap(){ memset(dis,0,sizeof(dis)); memset(gap,0,sizeof(gap)); memset(pre,-1,sizeof(pre)); for(int i=0;i<tot_num;i++) now[i]=head[i]; gap[0]=tot_num; int point=source,flow=0,min_flow=INT_INF; while(dis[source]<tot_num) { bool fg=false; for(int i=now[point];i!=-1;i=edge[i].next) if(edge[i].cap-edge[i].flow>0 && dis[point]==dis[edge[i].en]+1) { min_flow=min(min_flow,edge[i].cap-edge[i].flow); now[point]=i; pre[edge[i].en]=point; point=edge[i].en; if(point==sink) { flow+=min_flow; augment(min_flow); point=source; min_flow=INT_INF; } fg=true; break; } if(fg) continue; if(--gap[dis[point]]==0) break; int Min=tot_num; for(int i=head[point];i!=-1;i=edge[i].next) if(edge[i].cap-edge[i].flow>0 && Min>dis[edge[i].en]) { Min=dis[edge[i].en]; now[point]=i; } gap[dis[point]=Min+1]++; if(point!=source) point=pre[point]; } return flow;}char str[300010];int s[300010];int main(){ int n,m; int T,cas=0; gets(str); sscanf(str,"%d",&T); while(T--) { gets(str); gets(str); sscanf(str,"%d",&n); memset(s,0,sizeof(s)); memset(head,-1,sizeof(head)); tot=0; int sum=0; source=0; for(int i=1;i<=n;i++) { int t; int cnt=0,temp=0; gets(str); int P; int len=strlen(str); while(cnt<len-1) { bool pd=(cnt==0); sscanf(str+cnt,"%d%n",&t,&temp); cnt+=temp; if(pd) P=t; else { s[t]=i; } } sum+=P; add_edge(source,i,P); } gets(str); sscanf(str,"%d",&m); tot_num=n+m+2; sink=n+m+1; for(int i=1;i<=m;i++) { int t; int cnt=0,temp=0; gets(str); int P; int len=strlen(str); while(cnt<len-1) { bool pd=(cnt==0); sscanf(str+cnt,"%d%n",&t,&temp); cnt+=temp; if(pd) P=t; else { if(s[t]) { add_edge(s[t],i+n,INT_INF); } } } sum+=P; add_edge(i+n,sink,P); } int ans=sap(); printf("Case %d:n%dn",++cas,sum-ans); if(T) puts(""); } return 0;}
