#include #include #include #include #include #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 rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i)) #define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i)) #if defined(_MSC_VER) || __cplusplus > 199711L #define aut(r,v) auto r = (v) #else #define aut(r,v) __typeof(v) r = (v) #endif #define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it) #define all(o) (o).begin(), (o).end() #define pb(x) push_back(x) #define mp(x,y) make_pair((x),(y)) #define mset(m,v) memset(m,v,sizeof(m)) #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3fLL using namespace std; typedef vector vi; typedef pair pii; typedef vector > vpii; typedef long long ll; template inline void amin(T &x, U y) { if(y < x) x = y; } template inline void amax(T &x, U y) { if(x < y) x = y; } struct MaximumFlow { typedef int Index; typedef int Flow; static const Flow InfCapacity = INF; struct Edge { Index to; Flow capacity; Index rev; }; vector > g; void init(Index n) { g.assign(n, vector()); } void add(Index i, Index j, Flow capacity) { Edge e, f; e.to = j, f.to = i; e.capacity = capacity, f.capacity = 0; g[i].push_back(e); g[j].push_back(f); g[i].back().rev = (Index)g[j].size() - 1; g[j].back().rev = (Index)g[i].size() - 1; } void addB(Index i, Index j, Flow capacity) { Edge e, f; e.to = j, f.to = i; e.capacity = capacity, f.capacity = capacity; g[i].push_back(e); g[j].push_back(f); g[i].back().rev = (Index)g[j].size() - 1; g[j].back().rev = (Index)g[i].size() - 1; } //gを破壊する Flow maximumFlow(int s, int t) { int n = g.size(); vector level(n); Flow total = 0; bool update; do { update = false; fill(level.begin(), level.end(), -1); level[s] = 0; queue q; q.push(s); for(Index d = n; !q.empty() && level[q.front()] < d; ) { int u = q.front(); q.pop(); if(u == t) d = level[u]; each(e, g[u]) if(e->capacity > 0 && level[e->to] == -1) q.push(e->to), level[e->to] = level[u] + 1; } vector iter(n); for(Index i = 0; i < n; i ++) iter[i] = (int)g[i].size() - 1; while(1) { Flow f = augment(level, iter, s, t, InfCapacity); if(f == 0) break; total += f; update = true; } }while(update); return total; } Flow augment(vector &level, vector &iter, Index u, Index t, Flow f) { if(u == t || f == 0) return f; Index lv = level[u]; if(lv == -1) return 0; level[u] = -1; for(; iter[u] >= 0; -- iter[u]) { Edge &e = g[u][iter[u]]; if(level[e.to] <= lv) continue; Flow l = augment(level, iter, e.to, t, min(f, e.capacity)); if(l == 0) continue; e.capacity -= l; g[e.to][e.rev].capacity += l; level[u] = lv; return l; } return 0; } }; int main() { int W; scanf("%d", &W); int N; scanf("%d", &N); vector J(N); rep(i, N) scanf("%d", &J[i]); int M; scanf("%d", &M); vector C(M); rep(i, M) scanf("%d", &C[i]); int src = N + M, dst = src + 1; MaximumFlow mf; mf.init(dst + 1); rep(i, N) mf.add(src, i, J[i]); rep(i, M) { int Q; scanf("%d", &Q); vector ok(N, true); rep(j, Q) { int X; scanf("%d", &X), -- X; ok[X] = false; } rep(j, N) if(ok[j]) mf.add(j, N + i, INF); } rep(i, M) mf.add(N + i, dst, C[i]); int f = mf.maximumFlow(src, dst); bool ans = f >= W; puts(ans ? "SHIROBAKO" : "BANSAKUTSUKITA"); return 0; }