class FlowNetwork(object): def __init__(self): self.adj, self.flow, = {},{} def add_vertex(self, vertex): self.adj[vertex] = [] def get_edges(self, v): return self.adj[v] def add_edge(self, u,v,w=0): self.adj[u].append((v,w)) self.adj[v].append((u,0)) self.flow[(u,v)] = self.flow[(v,u)] = 0 def find_path(self, source, sink, path): if source == sink: return path for vertex, capacity in self.get_edges(source): residual = capacity - self.flow[(source,vertex)] edge = (source,vertex,residual) if residual > 0 and not edge in path: result = self.find_path(vertex, sink, path + [edge]) if result != None: return result def max_flow(self, source, sink): path = self.find_path(source, sink, []) while path != None: flow = min(r for u,v,r in path) for u,v,_ in path: self.flow[(u,v)] += flow self.flow[(v,u)] -= flow path = self.find_path(source, sink, []) return sum(self.flow[(source, vertex)] for vertex, capacity in self.get_edges(source)) numcases = input() for caseid in range(0,numcases): fn = FlowNetwork() sucetveci = 0 fn.add_vertex('source') fn.add_vertex('sink') nveci = input() nkuponov = input() for i in range(0,nveci): vec = input() sucetveci += vec fn.add_vertex('vec'+str(i)) fn.add_edge('vec'+str(i), 'sink', vec) for i in range(0,nkuponov): kupon = input() fn.add_vertex('kupon'+str(i)) fn.add_edge('source', 'kupon'+str(i), kupon) for i in range(0,nkuponov): nhran = input() for tmpid in range(0,nhran): vec = input()-1 fn.add_edge('kupon'+str(i), 'vec'+str(vec), 1e10000) print sucetveci - fn.max_flow('source', 'sink')