#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #ifdef _MSC_VER #include #endif #define FOR(i, a, b) for(int i = (a); i < (int)(b); ++i) #define rep(i, n) FOR(i, 0, n) #define ALL(v) v.begin(), v.end() #define REV(v) v.rbegin(), v.rend() #define MEMSET(v, s) memset(v, s, sizeof(v)) #define UNIQUE(v) (v).erase(unique(ALL(v)), (v).end()) #define MP make_pair #define MT make_tuple using namespace std; typedef long long ll; typedef long double ld; typedef pair P; class MaxFlow{ struct edge{ int to, rev, cap; edge(){} edge(int to, int rev, int cap) :to(to), rev(rev), cap(cap){} }; vector > Graph; vector used, level, iter; int V; static const int INF = 1 << 30; public: MaxFlow(int size) :V(size){ Graph.resize(V); iter.resize(V, 0); level.resize(V); used.resize(V, 0); } void add(int from, int to, int cap){ Graph[from].push_back(edge(to, Graph[to].size(), cap)); Graph[to].push_back(edge(from, Graph[from].size() - 1, 0)); } void dinic_bfs(int s){ fill(level.begin(), level.end(), -1); queue q; q.push(s); level[s] = 0; while (!q.empty()){ int v = q.front(); q.pop(); for (int i = 0; i < Graph[v].size(); i++){ edge &e = Graph[v][i]; if (e.cap <= 0 || level[e.to] >= 0) continue; level[e.to] = level[v] + 1; q.push(e.to); } } } int dinic_dfs(int s, int t, int f){ if (s == t) return f; for (int &i = iter[s]; i < Graph[s].size(); i++){ edge &e = Graph[s][i]; if (e.cap <= 0 || level[e.to] <= level[s]) continue; int res = dinic_dfs(e.to, t, min(f, e.cap)); if (res > 0){ e.cap -= res; Graph[e.to][e.rev].cap += res; return res; } } return 0; } int dinic(int s, int t){ int res = 0; while (1){ dinic_bfs(s); if (level[t] < 0) break; fill(iter.begin(), iter.end(), 0); int f; while (f = dinic_dfs(s, t, INF)){ res += f; } } return res; } int max_flow(int s, int t){ return dinic(s, t); } }; int main(){ cin.tie(0); ios::sync_with_stdio(false); cout.setf(ios::fixed); cout.precision(20); int w, n, m; cin >> w >> n; MaxFlow mf(102); const int SRC = 100, SNK = SRC + 1; rep(i, n){ int c; cin >> c; mf.add(SRC, i, c); } cin >> m; rep(i, m){ int c; cin >> c; mf.add(n + i, SNK, c); } rep(i, m){ int q; cin >> q; set st; rep(i, q){ int x; cin >> x; st.insert(x-1); } rep(j, n){ if (st.count(j)) continue; mf.add(j, n + i, w); } } bool ok = mf.max_flow(SRC, SNK) >= w; cout << (ok ? "SHIROBAKO" : "BANSAKUTSUKITA") << endl; }