////////////////////////////// // Check before you submit. // #define _ATCODER_LIBRARY const long long MOD = 1e9+7; // const long long MOD = 998244353; ///////////////////////////// #include using namespace std; #include using namespace boost::multiprecision; #ifdef _ATCODER_LIBRARY #include using namespace atcoder; #endif // _ATCODER_LIBRARY const long long INF = 1LL << 60; const double PI = acos(-1); using ll = long long; using P = array; #define FOR(i,a,b) for (ll i=(a);i<(ll)(b);++i) #define REP(i,n) FOR(i,0,n) #define ALL(v) (v).begin(),(v).end() #define SUM(v) accumulate(ALL(v),0ll) templateistream& operator>>(istream&i,vector&v){REP(j,v.size())i>>v[j];return i;} templatestring join(vector&v){stringstream s;REP(i,v.size())s<<' '<ostream& operator<<(ostream&o,vector&v){if(v.size())o<string join(vector>&vv){string s="\n";REP(i,vv.size())s+=join(vv[i])+"\n";return s;} templateostream& operator<<(ostream&o,vector>&vv){if(vv.size())o<istream& operator>>(istream&i,pair&v){return i>>v.first>>v.second;} templateostream& operator<<(ostream&o,pair&v){return o<<"("<istream& operator>>(istream&i,array&v){i>>v[0]>>v[1]; return i;} templateostream& operator<<(ostream&o,array&v){return o<<"("<T up(T a, T b){assert(b);return (a+b-1)/b;} templatebool eq(A const&... a){auto t={a...};assert(t.size());auto tar=*t.begin();for(const auto&e:t)if(tar!=e)return false;return true;} templatebool chmin(T &a, T b){if(a>b){a=b;return true;}return false;} templatebool chmax(T &a, T b){if(abool chmax(T &a, initializer_listl){return chmax(a,max(l));} templatebool chmin(T &a, initializer_listl){return chmin(a,min(l));} ////////////////////////////////////////////////////////////////// // My Library ////////////////////////////////////////////////////////////////// template class Dinic { private: int V; vector level,iter; void bfs(int s) { fill(level.begin(),level.end(),-1); queue que; level[s] = 0; que.push(s); while(!que.empty()){ int v = que.front(); que.pop(); for(auto& e : G[v]){ if(e.cap > 0 && level[e.to] < 0){ level[e.to] = level[v] + 1; que.push(e.to); } } } } T dfs(int v,int t,T 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]){ T 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; } public: struct edge{ int to; T cap; int rev; }; vector > G; Dinic(int node_size) : V(node_size), level(V), iter(V), G(V){} // Adding edge on a node. void add_edge(int from,int to,T cap) { G[from].push_back((edge){to,cap,(int)G[to].size()}); G[to].push_back((edge){from,(T)0,(int)G[from].size()-1}); } // Calculate the maximum flow. T solve(int s,int t) { T flow = 0; for(;;){ bfs(s); if(level[t] < 0) return flow; fill(iter.begin(),iter.end(),0); T f; while((f=dfs(s,t,numeric_limits::max())) > 0){ flow += f; } } } }; ////////////////////////////////////////////////////////////////// // Contest Code ////////////////////////////////////////////////////////////////// int main(int argc, char **argv) { init_init_init(); ll W, N; cin >> W >> N; vector J(N); cin >> J; ll M; cin >> M; vector C(M); cin >> C; vector> X(M); vector Q(M); REP(i, M) { cin >> Q[i]; REP(j, Q[i]) { ll a; cin >> a; --a; X[i].insert(a); } } ll start = N*2 + M*2; ll goal = start + 1; Dinic max_flow(N*2+M*2+10); REP(i, N) { max_flow.add_edge(start, i, INF); max_flow.add_edge(i, i+N, J[i]); } DEBUG("pass"); REP(i, N) { ll i2 = i+N; REP(j, M) { if (X[j].count(i)) continue; max_flow.add_edge(i2, 2*N+j, INF); } } DEBUG("pass2"); REP(j, M) { ll to = 2*N+M+j; max_flow.add_edge(2*N+j, to, C[j]); max_flow.add_edge(to, goal, INF); } DEBUG("pass3"); if (max_flow.solve(start, goal) >= W) std::cout << "SHIROBAKO"<< std::endl; else std::cout << "BANSAKUTSUKITA"<< std::endl; }