#include #include #include #include #include #include #include #include #include #include #include #include #define rep(i,n) for(int i = 0; i < n; ++i) #define rep1(i,n) for(int i = 1; i <= n; ++i) //#define rev(i,s,t) for(int i = s; i >= t; --i) using namespace std; templatebool chmax(T &a, const T &b) { if(a < b){ a = b; return 1; } return 0; } templatebool chmin(T &a, const T &b) { if(a > b){ a = b; return 1; } return 0; } template inline int sz(T &a) { return a.size(); } using ll = long long; using ld = long double; using pi = pair; using pl = pair; using vi = vector; using vvi = vector; using vl = vector; using vvl = vector; using PQ = priority_queue>; const int inf = numeric_limits::max(); const ll infll = numeric_limits::max(); vi dx = {1, 0, -1, 0}; vi dy = {0, 1, 0, -1}; template struct Vec2 { T X; T Y; bool operator == (const Vec2& r) const { return (X == r.X && Y == r.Y); } bool operator != (const Vec2& r) const { return !(*this == r); } bool operator < (const Vec2& r) const { if(X == r.X) return Y < r.Y; return X < r.X; } bool operator > (const Vec2& r) const { if(X == r.X) return Y > r.Y; return X > r.X; } }; // Modint // modint で宣言 template struct modint{ long long x; long long mod = MOD; modint(long long x=0):x(x%MOD){} modint& operator+=(const modint a){ if((x+=a.x)>=MOD) x-=MOD; return *this; } modint& operator-=(const modint a){ if((x += MOD-a.x)>=MOD) x-=MOD; return *this; } modint& operator*=(const modint a){ (x*=a.x)%=MOD; return *this; } modint operator+(const modint a) const{ modint res(*this); return res+=a; } modint operator-(const modint a) const{ modint res(*this); return res-=a; } modint operator*(const modint a) const{ modint res(*this); return res*=a; } modint pow(long long t) const{ if(!t) return 1; modint a = pow(t>>1); a*=a; if(t&1) a*=*this; return a; } modint inv() const{ return pow(MOD-2); } modint& operator/=(const modint a){ return (*this) *= a.inv(); } modint operator/(const modint a) const{ modint res(*this); return res/=a; } }; using mint = modint<1000000007>; using mint998 = modint<998244353>; using vm = vector; using vmm = vector; using vm998 = vector; using vmm998 = vector; const int NMAX=1000010; // we can calculate nCk until n is equal to NMAX mint fact[NMAX],infac[NMAX]; void Make_Fact(){ fact[0]=fact[1]=1; for(int i=2;i<=NMAX-1;++i){ fact[i]=fact[i-1]*(mint)i;}} void Make_InvFact(){ infac[0]=infac[1]=1; for(int i=2;i<=NMAX-1;++i){ infac[i]=infac[i-1]/(mint)i;}} mint Comb(int n,int k){ if(n<0||k<0||n-k<0) return 0; return fact[n]*infac[k]*infac[n-k]; } //---------------------------- // 抽象化セグ木 // 二項演算と単位元を渡して使ってね ///****例**************************** // auto f = [&](int a,int b){ return a+b;}; // 二項演算:和 // int id = 0; //単位元:0 // SegTree seg(f,id); //************************************ //---------------------------- template struct SegTree{ T identity; F merge; int size; vector dat; // 二項演算merge,単位元identify SegTree(F f,T id):merge(f),identity(id){} // 二項演算fと単位元idを渡して宣言する void init(int n){ size = 1; while(size<=n) size *= 2; dat.resize(size*2-1,identity); } // データの要素の数nを渡して初期化、sizeはnより大きい2の冪乗 void build(vector vec){ rep(i,vec.size()) dat[size-1+i] = vec[i]; dfs(0); } // 配列を渡して0(n)で初期化 T dfs(int k){ if(k>=size-1) return dat[k]; else return dat[k] = merge(dfs(2*k+1),dfs(2*k+2)); } // index kの要素をaに変更 void update(int k,T a){ k += size - 1; dat[k] = a; while(k > 0){ k = (k-1)/2; dat[k] = merge(dat[2*k+1],dat[2*k+2]); } } // index kの要素にaを加算 void add(int k,T a){ k += size - 1; dat[k] += a; while(k > 0){ k = (k-1)/2; dat[k] = merge(dat[2*k+1],dat[2*k+2]); }} // 区間[a,b)に対するクエリに答える。(k,l,r)=(0,0,size) T query(int a,int b,int k,int l,int r){ if(r<=a||b<=l) return identity; if(a<=l&&r<=b) return dat[k]; else return merge(query(a,b,2*k+1,l,(l+r)/2),query(a,b,2*k+2,(l+r)/2,r)); } T query(int a,int b){ return query(a, b, 0, 0, size); } // デバッグ用 void show(){ int index = 0; int num = 1; while(index par;//親 vector rank;//木の深さ vector size;//木の大きさ int n; UFT(int _n) { n = _n; par.resize(n); rank.assign(n,0); size.assign(n,1); rep(i,n){ par[i] = i; }} //xの根を返す int find(int x) { if(par[x] == x) return x; else return par[x] = find(par[x]);} //x,yを併合 void unite(int x,int y) { x = find(x); y = find(y); if(x == y) return; if(rank[x] < rank[y]){ par[x] = y; size[y] += size[x]; } else{ par[y] = x; size[x] += size[y]; if(rank[x] == rank[y]) rank[x]++; } } //x,yが同じグループにいるかどうかを返す bool same(int x,int y) { return find(x) == find(y); } //xの属する木のサイズを探す int usize(int x) { return size[find(x)]; } }; //**************************************** // MaxFlow // Graph gp(n); // gp.add_edge(from, to, capacity); // max_flow(s, t); //**************************************** // status of edge template struct Edge{ int from, to; int rev; //逆辺 X cap; // 容量 Edge() = default; Edge(int from, int to, int rev, X cap) : from(from), to(to), rev(rev), cap(cap) {} }; // status of node template struct Node{ int idx; vector> edge; //map idtable; // map[to] = val: node[idx]からnode[to]に出るedgeのindexを返す Node() = default; explicit Node(int idx) : idx(idx) {} }; template class Graph{ private: int n; // number of node int m; // number of edge vector> node; X inf = numeric_limits::max(); void Init_Node() { rep(i,n) node.emplace_back(i); } public: explicit Graph(int n) : n(n) { Init_Node(); } // 容量cap の辺を追加 void add_edge(int from, int to, X cap) { node[from].edge.emplace_back(from, to, node[to].edge.size(), cap); //node[from].idtable[to] = node[from].edge.size() - 1; node[to].edge.emplace_back(to, from, node[from].edge.size() - 1, 0); //node[to].idtable[from] = node[to].edge.size() - 1; } // from->toの辺(Edge<>)を返す // Edge get_edge(int from, int to) { // return node[from].edge[node[from].idtable[to]]; // } // s->tの最大流 X max_flow(int s, int t) { vi level(n); vi iter(n); auto bfs = [&]() { level.assign(n, -1); queue q; level[s] = 0; q.push(s); while( !q.empty() ) { int v = q.front(); q.pop(); for(auto next: node[v].edge) { if(next.cap > 0 && level[next.to] < 0) { level[next.to] = level[v] + 1; q.push(next.to); } } } }; auto dfs = [&](auto func, int v, X f) { if(v == t) return f; for(int &i = iter[v]; i < node[v].edge.size(); ++i) { Edge &e = node[v].edge[i]; if(e.cap > 0 && level[v] < level[e.to]) { X d = func(func, e.to, min(f, e.cap)); if(d > 0) { e.cap -= d; node[e.to].edge[e.rev].cap += d; return d; } } } return (X)0; }; // main X flow = 0; for(;;) { bfs(); if(level[t] < 0) return flow; iter.assign(n, 0); X f; while((f = dfs(dfs, s, inf)) > 0) { flow += f; } } } }; void Solve(){ int w; cin >> w; int n,m; cin >> n; vi a(n); rep(i,n) cin >> a[i]; cin >> m; vi c(m); rep(i,m) cin >> c[i]; vector> mp(m); rep(i,m) { int q; cin >> q; rep(j,q) { int x; cin >> x; x--; mp[i][x] = 1; } } Graph gp(n*2+m*2+2); rep(i,n) { gp.add_edge(i, n+m+i, a[i]); gp.add_edge(2*n+2*m, i, inf); } rep(i,m) { gp.add_edge(n+i, 2*n+m+i, c[i]); gp.add_edge(2*n+m+i, 2*n+2*m+1, inf); } rep(i,n) { rep(j,m) { if(mp[j].find(i) == mp[j].end()) { gp.add_edge(n+m+i, n+j, inf); } } } int res = gp.max_flow(2*n+2*m, 2*n+2*m+1); cout << (res >= w ? "SHIROBAKO" : "BANSAKUTSUKITA") << "\n"; } int main() { Solve(); return 0; }