#include using namespace std; const double EPS = 1e-6; void replace_basis(vector> &a, vector &id, int k, int j) { double r = a[k][j]; for (int i = 0; i < a[0].size(); i++) a[k][i] /= r; a[k][j] = 1; for (int i = 0; i < a.size(); i++) if (i != k) { double r = a[i][j]; for (int j = 0; j < a[i].size(); j++) a[i][j] -= a[k][j] * r; a[i][j] = 0; } id[k] = j; } void simplex(vector> &a, vector &id) { const int M = a.size() - 1; while (true) { int j = max_element(a[M].begin() + 1, a[M].end()) - a[M].begin(); if (a[M][j] < EPS) break; pair mn(1e100, INT_MAX); for (int i = 0; i < M; i++) { if (a[i][j] > EPS) mn = min(mn, make_pair(a[i][0] / a[i][j], i)); } int k = mn.second; replace_basis(a, id, k, j); } } // one-phase simplex double simplex1(vector> a, vector b, vector c) { const int M = a.size(); const int N = a[0].size(); vector> table(M + 1, vector(N + M + 1)); for (int i = 0; i < M; i++) { table[i][0] = b[i]; for (int j = 0; j < N; j++) { table[i][j + 1] = a[i][j]; } table[i][N + i + 1] = 1; } for (int i = 0; i < N; i++) table[M][i + 1] = c[i]; vector id(M); for (int i = 0; i < M; i++) id[i] = N + i + 1; simplex(table, id); return -table[M][0]; } // two-phase simplex // max sum c[i]*x[i] // s.t. sum(a[i][*]*x[i])<=b[i] double simplex(vector> a, vector b, vector c) { const int M = a.size(); const int N = a[0].size(); vector> table(M + 1, vector(N + M + 1)); for (int i = 0; i < M; i++) { table[i][0] = b[i]; for (int j = 0; j < N; j++) { table[i][j + 1] = a[i][j]; table[M][j + 1] += a[i][j]; } table[M][0] += b[i]; table[i][N + i + 1] = 1; } vector id(M); for (int i = 0; i < M; i++) id[i] = N + i + 1; simplex(table, id); for (int i = 0; i < M; i++) { if (id[i] >= N + 1) { int j; for (j = 1; j <= N; j++) { if (abs(table[i][j]) > EPS) break; } if (j == N + 1) return -1e100; replace_basis(table, id, i, j); } } for (int i = 0; i <= M; i++) { table[i].resize(N + 1); } table[M][0] = 0; for (int i = 0; i < N; i++) { table[M][i + 1] = c[i]; } for (int i = 0; i < M; i++) { double r = table[M][id[i]]; for (int j = 0; j <= N; j++) { table[M][j] -= table[i][j] * r; } } simplex(table, id); return -table[M][0]; } // one-phase simplex struct MaxFlowLP2 { int n; vector cap; vector> in, out; int es; MaxFlowLP2(int n) : n(n), in(n), out(n), es(0) { } void add(int u, int v, int c) { cap.push_back(c); out[u].push_back(es); in[v].push_back(es); es++; } int calc(int s, int t) { vector> a; vector b; vector c(es); for (int i = 0; i < es; i++) { vector t(es); t[i] = 1; a.push_back(t); b.push_back(cap[i]); } for (int i = 0; i < n; i++) { if (i != s && i != t) { vector t(es), tt(es); for (int j : out[i]) t[j]++, tt[j]--; for (int j : in[i]) t[j]--, tt[j]++; a.push_back(t); b.push_back(EPS); a.push_back(tt); b.push_back(EPS); } } for (int j : out[s]) c[j]++; for (int j : in[s]) c[j]--; return round(simplex1(a, b, c)); } }; // two-phase simplex struct MaxFlowLP { int n; vector cap; vector> in, out; int es; MaxFlowLP(int n) : n(n), in(n), out(n), es(0) { } void add(int u, int v, int c) { cap.push_back(c); out[u].push_back(es); in[v].push_back(es); es++; } int calc(int s, int t) { vector> a; vector b; vector c(es * 2); for (int i = 0; i < es; i++) { vector t(es * 2); t[i] = t[i + es] = 1; a.push_back(t); b.push_back(cap[i]); } for (int i = 0; i < n; i++) { if (i != s && i != t && (!in[i].empty() || !out[i].empty())) { vector t(es * 2); for (int j : out[i]) t[j]++; for (int j : in[i]) t[j]--; a.push_back(t); b.push_back(0); } } for (int j : out[s]) c[j]++; for (int j : in[s]) c[j]--; return round(simplex(a, b, c)); } }; int main() { int w; cin >> w; int n; cin >> n; vector J(n); for (int i = 0; i < n; i++) { scanf("%d", &J[i]); } int m; cin >> m; vector c(m); for (int i = 0; i < m; i++) { scanf("%d", &c[i]); } vector> bad(n, vector(m)); for (int i = 0; i < m; i++) { int q; cin >> q; for (int j = 0; j < q; j++) { int x; cin >> x; x--; bad[x][i] = true; } } MaxFlowLP2 mf(n + m + 2); int src = n + m; int dst = src + 1; for (int i = 0; i < n; i++) { mf.add(src, i, J[i]); } for (int i = 0; i < m; i++) { mf.add(i + n, dst, c[i]); } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (!bad[i][j]) { mf.add(i, j + n, 10101010); } } } int f = mf.calc(src, dst); if (f >= w) { cout << "SHIROBAKO" << endl; } else { cout << "BANSAKUTSUKITA" << endl; } }