module main; // https://mayokoex.hatenablog.com/entry/2015/04/03/082450 より // 最大フロー import std; // https://ei1333.github.io/library/graph/flow/dinic.hpp より struct Dinic(Flow) { immutable Flow INF; struct Edge { int to; Flow cap; int rev; bool isRev; int idx; } Edge[][] graph; int[] minCost, iter; // コンストラクタ this(int V) { INF = Flow.max; graph.length = V; } void addEdge(int from ,int to, Flow cap, int idx = -1) { graph[from] ~= Edge(to, cap, graph[to].length.to!int, false, idx); graph[to] ~= Edge(from, 0, graph[from].length.to!int - 1, true, idx); } bool buildAugmentPath(int s, int t) { minCost = uninitializedArray!(int[])(graph.length); minCost[] = -1; minCost[s] = 0; auto que = DList!int(s); while (!que.empty && minCost[t] == -1) { int p = que.front; que.removeFront; foreach (e; graph[p]) { if (e.cap <= 0 || minCost[e.to] != -1) continue; minCost[e.to] = minCost[p] + 1; que.insertBack(e.to); } } return minCost[t] != -1; } Flow findMinDistAugmentPath(int idx, in int t, Flow flow) { if (idx == t) return flow; for (int* i = &iter[idx]; *i < graph[idx].length; (*i)++) { Edge* e = &graph[idx][*i]; if (e.cap <= 0 || minCost[idx] >= minCost[e.to]) continue; Flow d = findMinDistAugmentPath(e.to, t, min(flow, e.cap)); if (d > 0) { e.cap -= d; graph[e.to][e.rev].cap += d; return d; } } return 0; } Flow maxFlow(int s, int t) { Flow flow = 0; while (buildAugmentPath(s, t)) { iter = new int[](graph.length); Flow f; while ((f = findMinDistAugmentPath(s, t, INF)) > 0) flow += f; } return flow; } void output() { foreach (i; 0 .. graph.length) { foreach (e; graph[i]) { if (e.isRev) continue; auto revE = graph[e.to][e.rev]; writefln("%d->%d (flow: %d/%d)", i, e.to, revE.cap, e.cap + revE.cap); } } } bool[] minCut(int s) { auto used = new bool[](graph.length); used[s] = true; auto que = DList!int(s); while (!que.empty) { int p = que.front; que.removeFront; foreach (e; graph[p]) { if (e.cap <= 0 || used[e.to]) continue; used[e.to] = true; que.insertBack(e.to); } } return used; } } void main() { // 入力 int W = readln.chomp.to!int; int N = readln.chomp.to!int; auto J = readln.split.to!(int[]); int M = readln.chomp.to!int; auto C = readln.split.to!(int[]); auto ng = new bool[][](M, N); foreach (i; 0 .. M) { auto Q = readln.split.to!(int[]); foreach (x; Q[1 .. $]) { ng[i][x - 1] = true; } } // 答えの計算 const s = N + M + 1, t = s + 1, V = t + 1; auto dinic = Dinic!int(V); foreach (i; 0 .. N) dinic.addEdge(s, i, J[i]); foreach (i; 0 .. M) { dinic.addEdge(i + N, t, C[i]); foreach (j; 0 .. N) { if (!ng[i][j]) dinic.addEdge(j, i + N, J[j]); } } int flow = dinic.maxFlow(s, t); // 答えの出力 writeln(flow >= W ? "SHIROBAKO" : "BANSAKUTSUKITA"); }