import std.algorithm, std.container, std.conv, std.math, std.range, std.typecons, std.stdio, std.string; auto rdsp(){return readln.splitter;} void pick(R,T)(ref R r,ref T t){t=r.front.to!T;r.popFront;} void readV(T...)(ref T t){auto r=rdsp;foreach(ref v;t)pick(r,v);} void readA(T)(size_t n,ref T[]t){t=new T[](n);auto r=rdsp;foreach(ref v;t)pick(r,v);} void main() { int w; readV(w); int n; readV(n); int[] j; readA(n, j); int m; readV(m); int[] c; readA(m, c); auto g = GraphW!int(n+m+2); foreach (i; 0..n) g.addEdge(n+m, i, j[i]); foreach (i; 0..m) g.addEdge(n+i, n+m+1, c[i]); foreach (i; 0..m) { auto rd = rdsp; int q; pick(rd, q); auto x = new int[](q); foreach (k; 0..q) pick(rd, x[k]); --x[]; foreach (k; 0..n) if (!x.canFind(k)) g.addEdge(k, n+i, g.inf); } writeln(g.dinic(n+m, n+m+1) >= w ? "SHIROBAKO" : "BANSAKUTSUKITA"); } struct GraphW(N = int, W = int, W i = 10^^9) { alias Node = N, Wt = W, inf = i; struct Edge { Node src, dst; Wt wt; alias cap = wt; } Node n; Edge[][] g; alias g this; this(Node n) { this.n = n; g = new Edge[][](n); } void addEdge(Node u, Node v, Wt w) { g[u] ~= Edge(u, v, w); } void addEdgeB(Node u, Node v, Wt w) { g[u] ~= Edge(u, v, w); g[v] ~= Edge(v, u, w); } } template Dinic(Graph) { import std.algorithm, std.container, std.traits; alias Node = TemplateArgsOf!Graph[0], Wt = TemplateArgsOf!Graph[1]; struct EdgeR { Node src, dst; Wt cap, flow; Node rev; } Wt dinic(ref Graph g, Node s, Node t) { auto n = g.n, adj = withRev(g, n), level = new int[](n); auto levelize() { level[] = -1; level[s] = 0; auto q = DList!Node(s); while (!q.empty) { auto u = q.front; q.removeFront(); if (u == t) break; foreach (ref e; adj[u]) if (e.cap > e.flow && level[e.dst] < 0) { q.insertBack(e.dst); level[e.dst] = level[u] + 1; } } return level[t]; } Wt augment(Node u, Wt cur) { if (u == t) return cur; foreach (ref e; adj[u]) { auto r = &adj[e.dst][e.rev]; if (e.cap > e.flow && level[u] < level[e.dst]) { auto f = augment(e.dst, min(cur, e.cap - e.flow)); if (f > 0) { e.flow += f; r.flow -= f; return f; } } } return 0; } Wt flow = 0, f = 0; while (levelize >= 0) while ((f = augment(s, g.inf)) > 0) flow += f; return flow; } EdgeR[][] withRev(ref Graph g, Node n) { auto r = new EdgeR[][](n); foreach (gi; g) foreach (e; gi) { r[e.src] ~= EdgeR(e.src, e.dst, e.cap, 0, cast(Node)(r[e.dst].length)); r[e.dst] ~= EdgeR(e.dst, e.src, 0, 0, cast(Node)(r[e.src].length) - 1); } return r; } } auto dinic(G, N)(G g, N s, N t) { return Dinic!G.dinic(g, s, t); }