#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define BET(a,b,c) ((a)<=(b)&&(b)<(c)) #define FOR(i,n) for(int i=0,i##_end=(int(n));i VI; typedef vector VVI; typedef int weight; weight INF = 1<<28; const int MAXV = 200;//102; class Dinic { int n; weight capacity[MAXV][MAXV] , flow[MAXV][MAXV]; int level[MAXV] ; bool used[MAXV]; vector > adj; public : Dinic(int n) : n(n) , adj(n) { memset(capacity , 0 , sizeof(capacity)); } void add_edge(int from , int to , weight flow) { if(capacity[from][to]==0 && flow){ adj[from].push_back(to); adj[to].push_back(from); } capacity[from][to] += flow; } weight get_flow(int from , int to){ return flow[from][to]-flow[to][from]; } weight residue(int from,int to) { return capacity[from][to]-get_flow(from,to) ; } weight augment(int pos, int end , weight cur) { weight flow_out = 0 ; vector::const_iterator it = adj[pos].begin() , it_end = adj[pos].end(); for(; it != it_end ; it++){ int i = *it; if (level[i]==level[pos]+1) { weight f = min(cur - flow_out , residue(pos,i)) ; if(f<=0) continue; if (i==end ||(!used[i] && (f = augment(i , end , f)) > 0)) { flow[pos][i] += f; flow_out += f ; if(cur-flow_out==0) return flow_out ; } } } used[pos] = flow_out == 0; return flow_out; } bool levelize(int s ,int t){ memset(level , -1 , sizeof(level)); queue q; level[s] = 0; q.push(s); while(!q.empty()) { int pos = q.front(); q.pop(); vector::const_iterator it = adj[pos].begin() , it_end = adj[pos].end(); for(; it != it_end ; it++){ int dest = *it; if (level[dest] == -1 && residue(pos, dest) > 0) { level[dest] = level[pos] + 1; q.push(dest); } } } return (level[t]!=-1) ; } weight run(int s, int t) { memset(flow , 0 , sizeof(flow)); weight flow_sum=0; while(levelize(s,t)) { fill_n(used , n , false); flow_sum += augment(s, t , INF); } return flow_sum; } }; int main() { int W; int N; cin>>W>>N; VI J(N); FOR(i,N) cin>>J[i]; int M; cin>>M; VI C(M); FOR(i,M) cin>>C[i]; int source = N + M; int sink = source + 1; Dinic D(sink + 1); FOR(i,M){ int q; cin>>q; VI fit(N, 1); FOR(_,q){ int x; scanf("%d",&x); x--; fit[x] = 0; } FOR(j, N){ if(fit[j]) D.add_edge(j, N + i, 1<<28); } } FOR(i,N) D.add_edge(source, i, J[i]); FOR(i,M) D.add_edge(N+i, sink, C[i]); puts(D.run(source,sink) >= W ? "SHIROBAKO" : "BANSAKUTSUKITA"); return 0; }