#include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; #define reps(i,s,n) for(int (i) = (s); (i) < (n); (i)++) #define rep(i,n) reps(i,0,n) const int INF = 1e9; struct edge{int to,cap,rev;};//行き先、容量、逆辺 const int MAX_V = 2e4; vector G[MAX_V]; bool used[MAX_V]; int W,N,M; int f,to,c; int q,x; vector J,C; //from->toへ容量capの辺を追加 void add_edge(int from ,int to ,int cap){ //行き先、容量、逆辺 G[from].push_back({to,cap,(int)G[to].size()});//(行き先to,容量cap,) G[to].size() := 行き先toから伸びる辺の数 G[to].push_back({from,0,(int)G[from].size()-1});//(現在地from,容量0,) G[from].size()-1:= 現在地fromから伸びる辺-1 //↑戻る時、既に1本の辺については考えられている? } //増加パス? int dfs(int v,int t,int f){ if(v == t) return f; used[v] = true; rep(i,G[v].size()){ edge &e = G[v][i];//頂点vから伸びるi番目の辺 行き先、容量、行き先から伸びる数 // if(!used[e.to] && e.cap > 0){ int d = dfs(e.to, t, min(f,e.cap));//e.to -> t,容量min(f,e.cap) :=目いっぱい流す if(d > 0){ e.cap -= d;//空き容量をd減らす G[e.to][e.rev].cap += d;//e.toのe.rev番目の容量| 元に戻せる量をd増やす return d; } } } return 0; } int max_flow(int s,int t){ int flow = 0; for(;;){ memset(used,0,sizeof(used)); int f = dfs(s,t,INF); if(f == 0) return flow; flow += f; } } int main(){ cin >> W; cin >> N; J.resize(N); rep(i,N){ cin >> J[i]; //N番目まで i番目の原画(入)はi+1で表現 //i番目の原画(出)はi+(N+1)で表現 add_edge(0,i+1,J[i]); add_edge(i+1,i+(N+1),J[i]); } cin >> M; C.resize(M); rep(i,M){ cin >> C[i]; //作画の入頂点から出頂点に辺をはる add_edge((2*N+1)+i,(2*N+M+1)+i,C[i]); //各作画-> 終点にCiの辺をはる add_edge((2*N+M+1)+i,(2*N+2*M)+1,C[i]); } vector list; rep(i,M){ list.clear(); rep(j,N) list.push_back(j); cin >> q; rep(j,q){ cin >> x; x--;//0オリジンに list[x] = -1; //xに含まれない作画に辺をはる。 } rep(j,N){//-1であれば相性が悪い。-1でない要素について辺をはる if(list[j] != -1) add_edge(list[j]+N+1,i+(2*N+1),J[list[j]]); } } if(max_flow(0,2*N+2*M+1) >= W){ cout << "SHIROBAKO" << endl; }else{ cout << "BANSAKUTSUKITA" << endl; } return 0; }