// yukicoder: No.177 制作進行の宮森あおいです // 2019.7.21 bal4u #include #include #if 1 #define gc() getchar_unlocked() #else #define gc() getchar() #endif int in() { // 非負整数の入力 int n = 0, c = gc(); do n = 10 * n + (c & 0xf); while ((c = gc()) >= '0'); return n; } /*******************************************/ /* Dinic's Max Flow Algorithm /*******************************************/ #define INF 0x01010101 #define VMAX 105 typedef struct { int to; int cap; int rev; } EDGE; EDGE edge[VMAX][VMAX]; int hi[VMAX]; int V; // 頂点数 int level[VMAX], iter[VMAX]; int queue[VMAX], qtop; void add_edge(int from, int to, int cap) { int f, t; EDGE *e; f = hi[from]++, t = hi[to]++; e = &edge[from][f], e->to = to, e->cap = cap, e->rev = t; // e = &edge[to][t], e->to = from, e->cap = 0, e->rev = f; e = &edge[to][t], e->to = from, e->cap = cap, e->rev = f; } void bfs(int s) { int i, v; EDGE *e; memset(level, -1, sizeof(int)*V); level[s] = 0; queue[0] = s, qtop = 1; while (qtop) { v = queue[--qtop]; for (i = 0; i < hi[v]; i++) { e = &edge[v][i]; if (e->cap > 0 && level[e->to] < 0) { level[e->to] = level[v] + 1; queue[qtop++] = e->to; } } } } int dfs(int v, int t, int f) { int *i, d; EDGE *e; if (v == t) return f; for (i = &iter[v]; *i < hi[v]; (*i)++) { e = &edge[v][*i]; if (e->cap > 0 && level[v] < level[e->to]) { d = dfs(e->to, t, f <= e->cap? f: e->cap); if (d > 0) { e->cap -= d; edge[e->to][e->rev].cap += d; return d; } } } return 0; } int maxFlow(int s, int t) { int f, flow = 0; while (1) { bfs(s); if (level[t] < 0) break; memset(iter, 0, sizeof(int)*V); while ((f = dfs(s, t, INF)) > 0) flow += f; } return flow; } /**********************************************/ int J[53]; char f[53]; int main() { int i, j, W, N, M, S, T, Q; W = in(); S = 0, T = 1; N = in(); for (i = 0; i < N; i++) add_edge(S, 2+i, J[i] = in()); // 各原画マンが描ける絵の数 M = in(); for (i = 0; i < M; i++) add_edge(N+2+i, T, in()); // 各監督が仕上げる絵の数 for (i = 0; i < M; i++) { memset(f, 0, sizeof(f)); Q = in(); while (Q--) f[in()-1] = 1; for (j = 0; j < N; j++) if (!f[j]) add_edge(2+j, N+2+i, J[j]); // 相性のいい原画マンと監督 } V = 2 + N + M; puts(maxFlow(S, T) >= W? "SHIROBAKO": "BANSAKUTSUKITA"); return 0; }