/* tester : atetubou's code */ #include #include #include #include #include #include #include #include #include #include #include #include #define rep(i,n) for(int i=0;i<(int)(n);++i) #define F first #define S second #define SZ(a) (int)((a).size()) #define sz(a) SZ(a) #define pb(a) push_back(a) #define mp(a,b) make_pair(a,b) #define ALL(a) (a).begin(),(a).end() using namespace std; typedef long long ll; typedef pair PI; typedef unsigned long long ull; #define PR(...) do{cerr << "line : " << __LINE__ << endl; pr(#__VA_ARGS__, __VA_ARGS__);}while(0); template void pr(const string& name, T t){ cerr << name << ": " << t << endl; } template void pr(const string& names, T t, Types ... rest) { auto comma_pos = names.find(','); cerr << names.substr(0, comma_pos) << ": " << t << ", "; auto next_name_pos = names.find_first_not_of(" \t\n", comma_pos + 1); pr(string(names, next_name_pos), rest ...); } template ostream& operator<< (ostream& o, const pair& v){return o << "(" << v.F << ", " << v.S << ")";} template ostream& operator<< (ostream& o, const vector& v){o << "{";rep(i,SZ(v)) o << (i?", ":"") << v[i];return o << "}";} #define endl '\n' struct FlowGraphD{ /* verified http://poj.org/problem?id=3469 http://poj.org/problem?id=2987 */ typedef ll Cap; struct edge{ int to,rev; Cap cap; edge(int _to,Cap _cap,int _rev): to(_to),rev(_rev),cap(_cap){}; }; vector > G; vector iter,level; void add_edge(int from,int to,Cap cap){ G[from].push_back(edge(to,cap,G[to].size())); G[to].push_back(edge(from,0,G[from].size()-1)); } FlowGraphD(int V):G(V),iter(V),level(V){}; void bfs(int s){ fill(level.begin(),level.end(),-1); queue > q; q.push(make_pair(s,0)); while(!q.empty()){ int cv = q.front().first; int cc = q.front().second; q.pop(); if(level[cv] != -1) continue; level[cv] = cc; for(int i = 0; i < (int)G[cv].size(); ++i){ edge& e = G[cv][i]; if(e.cap > 0 && level[e.to] == -1) q.push(make_pair(e.to,cc+1)); } } } Cap dfs(int v,int t,Cap f){ if(v == t) return f; for(int& i = iter[v]; i < (int)G[v].size(); ++i){ edge& e = G[v][i]; if(e.cap > 0 && level[v] < level[e.to]){ Cap d = dfs(e.to, t, min(f, e.cap)); if(d > 0){ e.cap -= d; G[e.to][e.rev].cap += d; return d; } } } return 0; } Cap max_flow(int s, int t){ Cap flow = 0; // ll sum = 0; // for(int i = 0; i < (int)G[s].size(); ++i) // sum += G[s][i].cap; for(;;){ bfs(s); if(level[t] < 0) break; fill(iter.begin(), iter.end(), 0); Cap f; while((f = dfs(s, t,1LL << 30LL)) > 0){ flow += f; //sum -= f; } } return flow; } }; int main(int argc, char *argv[]) { int w,n; cin >> w >> n; vector J(n); rep(j,n) cin >> J[j]; int m; cin >> m; FlowGraphD fg(n+m+2); int source = n+m; int target = source+1; rep(j,n) fg.add_edge(source,j,J[j]); rep(j,m){ int c; cin >> c; fg.add_edge(j+n,target,c); } rep(i,m){ int qi; cin >> qi; set app; rep(j,qi){ int x; cin >> x; --x; app.insert(x); } rep(j,n) if(!app.count(j)) fg.add_edge(j,i+n,w); } auto now_w = fg.max_flow(source,target); //cout << "now_w" << "=" << now_w << endl; cout << (now_w>=w?"SHIROBAKO":"BANSAKUTSUKITA") << endl; return 0; }