#include #include #include #define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++) using namespace std; typedef vector VI; /** * Dinic's algorithm for maximum flow problem. * Header requirement: vector, queue * Verified by: ABC010-D(http://abc010.contest.atcoder.jp/submissions/602810) * ARC031-D(http://arc031.contest.atcoder.jp/submissions/1050071) * POJ 3155(http://poj.org/problem?id=3155) */ template class Dinic { private: struct edge { int to; T cap; int rev; // rev is the position of reverse edge in graph[to] }; std::vector > graph; std::vector level; std::vector iter; /* Perform bfs and calculate distance from s */ void bfs(int s) { level.assign(level.size(), -1); std::queue que; level[s] = 0; que.push(s); while (! que.empty()) { int v = que.front(); que.pop(); for (int i = 0; i < graph[v].size(); ++i) { edge &e = graph[v][i]; if (e.cap > 0 && level[e.to] == -1) { level[e.to] = level[v] + 1; que.push(e.to); } } } } /* search augment path by dfs. if f == -1, f is treated as infinity. */ T dfs(int v, int t, T f) { if (v == t) { return f; } for (int &i = iter[v]; i < graph[v].size(); ++i) { edge &e = graph[v][i]; if (e.cap > 0 && level[v] < level[e.to]) { T newf = f == -1 ? e.cap : std::min(f, e.cap); T d = dfs(e.to, t, newf); if (d > 0) { e.cap -= d; graph[e.to][e.rev].cap += d; return d; } } } return 0; } public: /* v is the number of vertices (labeled from 0 .. v-1) */ Dinic(int v) : graph(v), level(v, -1), iter(v, 0) {} void add_edge(int from, int to, T cap) { graph[from].push_back((edge) {to, cap, graph[to].size()}); graph[to].push_back((edge) {from, 0, graph[from].size() - 1}); } T max_flow(int s, int t) { T flow = 0; while (1) { bfs(s); if (level[t] < 0) { return flow; } iter.assign(iter.size(), 0); T f; while ((f = dfs(s, t, -1)) > 0) { flow += f; } } } std::pair > max_flow_cut(int s, int t) { T flow = 0; while (1) { bfs(s); if (level[t] < 0) { std::vector ret; for (int i = 0; i < graph.size(); ++i) { if (level[i] < 0) { ret.push_back(i); } } return std::pair >(flow, ret); } iter.assign(iter.size(), 0); T f; while ((f = dfs(s, t, -1)) > 0) { flow += f; } } } }; int main(void){ int w, n; cin >> w >> n; VI j(n); REP(i, 0, n) { cin >> j[i]; } int m; cin >> m; VI c(m); REP(i, 0, m) { cin >> c[i]; } Dinic din(n + m + 2); REP(i, 0, n) { din.add_edge(0, 2 + i, j[i]); } REP(i, 0, m) { din.add_edge(2 + n + i, 1, c[i]); } REP(i, 0, m) { int qi; cin >> qi; VI lim(n, 1e8); REP(j, 0, qi) { int x; cin >> x; x--; lim[x] = 0; } REP(j, 0, n) { din.add_edge(2 + j, 2 + n + i, lim[j]); } } cout << (din.max_flow(0, 1) >= w ? "SHIROBAKO" : "BANSAKUTSUKITA") << endl; }