from collections import deque class Edge: def __init__(self, to, rev, cap): self.to = to self.rev = rev self.cap = cap class MaxFlow: def __init__(self, n): self.size = n self.graph = [[] for _ in range(n)] def add_edge(self, fr, to, cap): forward = Edge(to, len(self.graph[to]), cap) backward = Edge(fr, len(self.graph[fr]), 0) self.graph[fr].append(forward) self.graph[to].append(backward) def bfs_level(self, s, t, level): q = deque() level[:] = [-1] * self.size level[s] = 0 q.append(s) while q: v = q.popleft() for edge in self.graph[v]: if edge.cap > 0 and level[edge.to] < 0: level[edge.to] = level[v] + 1 q.append(edge.to) if edge.to == t: return def dfs_flow(self, v, t, upTo, iter_, level): if v == t: return upTo for i in range(iter_[v], len(self.graph[v])): edge = self.graph[v][i] if edge.cap > 0 and level[v] < level[edge.to]: d = self.dfs_flow(edge.to, t, min(upTo, edge.cap), iter_, level) if d > 0: edge.cap -= d self.graph[edge.to][edge.rev].cap += d return d iter_[v] += 1 return 0 def max_flow(self, s, t): flow = 0 level = [-1] * self.size while True: self.bfs_level(s, t, level) if level[t] < 0: return flow iter_ = [0] * self.size while True: f = self.dfs_flow(s, t, float('inf'), iter_, level) if f == 0: break flow += f level = [-1] * self.size return flow def main(): import sys input = sys.stdin.read().split() ptr = 0 W = int(input[ptr]) ptr +=1 N = int(input[ptr]) ptr +=1 J = list(map(int, input[ptr:ptr+N])) ptr +=N M = int(input[ptr]) ptr +=1 C = list(map(int, input[ptr:ptr+M])) ptr +=M excluded = [set() for _ in range(M)] for j in range(M): Qj = int(input[ptr]) ptr +=1 Xs = list(map(int, input[ptr:ptr+Qj])) ptr +=Qj for x in Xs: excluded[j].add(x-1) # Convert to 0-based illustrator index # Check sum_J first sum_J = sum(J) if sum_J < W: print("BANSAKUTSUKITA") return # Build the flow network total_nodes = 1 + N + M +1 # S=0, illustrators 1..N, supervisors N+1..N+M, T=N+M+1 mf = MaxFlow(total_nodes) S = 0 T = N + M +1 # Add edges from S to illustrators for i in range(1, N+1): # illustrator i (node i) corresponds to 0-based index i-1 capacity = J[i-1] mf.add_edge(S, i, capacity) # Add edges from illustrators to supervisors where allowed INF = 10**18 for i_node in range(1, N+1): illustrator_0index = i_node -1 for j in range(M): # j is 0-based supervisor index if illustrator_0index not in excluded[j]: supervisor_node = N+1 + j mf.add_edge(i_node, supervisor_node, INF) # Add edges from supervisors to T for j in range(M): supervisor_node = N+1 +j capacity = C[j] mf.add_edge(supervisor_node, T, capacity) max_flow = mf.max_flow(S, T) if max_flow >= W: print("SHIROBAKO") else: print("BANSAKUTSUKITA") if __name__ == "__main__": main()