#dfsするやつ def dfs (graph, used, from, sink, flow) return flow if from == sink used[from] = true graph[from].each{|edge| #edgeのtoがdfs済み or edgeのcapが0以下のときは次 next if used[edge[0]] || (edge[1]<=0) #flowとedgeのcapの小さい方をfminに入れている #fmin = edge[1] #fmin = flow if fmin > flow #dfsを投げる。流せる分が返ってくる。 d = dfs(graph, used, edge[0], sink, [edge[1],flow].min) #流した分capを減らす。流した分逆流させる事ができるので、逆辺のcapを流した分増やす。 if d > 0 then #edgeのcap edge[1] -= d #グラフのedgeのtoの逆辺(rev)のcap graph[edge[0]][edge[2]][1] += d return d end } return 0 end w = gets.to_i n = gets.to_i j = gets.split.map &:to_i m = gets.to_i c = gets.split.map &:to_i # inf = 100000000 # source = 0 sink = n+m+1 #n個,それぞれに[to,cap,rev]を追加していく graph = (n+m+2).times.map{[]} #調べたか used = Array.new(n+m+2, false) #addedge x = m.times.map{|i| dame = Array.new(n, false) q,*x = gets.split.map &:to_i x.each{|k|dame[k-1] = true} n.times{|j| if !dame[j] then graph[j+1]<<[n+i+1,inf,graph[n+i+1].size] graph[n+i+1]<<[j+1,0,graph[j+1].size-1] end } } # n.times{|i| graph[source]<<[i+1,j[i],graph[i+1].size] graph[i+1]<<[source,0,graph[source].size-1] } # m.times{|i| graph[n+i+1]<<[sink,c[i],graph[sink].size] graph[sink]<<[n+i+1,0,graph[n+i+1].size-1] } #fordFulkerson flow = 0 while 1 (n+m+2).times{|i| used[i]=false} f = dfs(graph, used, source, sink, inf) break if f==0 flow += f end puts (flow>=w)?'SHIROBAKO':'BANSAKUTSUKITA'