/*
很明显的最大权闭合图题
*/
#include
  
   
#include
   
     #include
    
      using namespace std; #define N 2100 #define inf 0x3fffffff struct node { int u,v,w,next; }bian[N*N*20]; int head[N],yong,dis[N],work[N]; void init(){ yong=0; memset(head,-1,sizeof(head)); } void addbian(int u,int v,int w) { bian[yong].u=u; bian[yong].v=v; bian[yong].w=w; bian[yong].next=head[u]; head[u]=yong++; } void add(int u,int v,int w) { addbian(u,v,w); addbian(v,u,0); } int min(int a,int b) { return a
     
      q; q.push(s); dis[s]=0; while(!q.empty()) { int u=q.front(); q.pop(); for(int i=head[u];i!=-1;i=bian[i].next) { int v=bian[i].v; if(bian[i].w&&dis[v]==-1) { dis[v]=dis[u]+1; q.push(v); if(v==t) return 1; } } } return 0; } int dfs(int s,int limit,int t) { if(s==t)return limit; for(int &i=work[s];i!=-1;i=bian[i].next) { int v=bian[i].v; if(bian[i].w&&dis[v]==dis[s]+1) { int tt=dfs(v,min(limit,bian[i].w),t); if(tt) { bian[i].w-=tt; bian[i^1].w+=tt; return tt; } } } return 0; } int dinic(int s,int t) { int ans=0; while(bfs(s,t)) { memcpy(work,head,sizeof(head)); while(int tt=dfs(s,inf,t)) ans+=tt; } return ans; } int main() { int t,n,m,i,j,k,S,T,e,cost[N],total,cou=0; scanf("%d",&t); while(t--) { init(); scanf("%d%d",&n,&m); T=n+m+1;S=0; total=0; for(i=1;i<=n;i++) { scanf("%d",&j); total+=j; add(S,i,j); } for(i=1;i<=m;i++) scanf("%d",&cost[i]); for(i=1;i<=n;i++) { scanf("%d",&k); while(k--) { scanf("%d",&j); j++; add(i,n+j,inf); } } for(i=1;i<=m;i++) for(j=1;j<=m;j++) { scanf("%d",&e); if(e) add(i+n,j+n,inf); } for(i=n+1;i<=n+m;i++) add(i,T,cost[i-n]); printf("Case #%d: ",++cou); printf("%d\n",total-dinic(S,T)); } return 0;}