#include #define rep(i, n) for (int i=0; i<(int)(n); i++) #define all(v) v.begin(), v.end() #define PRINT(v) for (auto x : (v)) cout <>; using mat = vector>; const ll MOD = 1000000007; const ll INF = 10000000000000000; vector x4 = {0, 1, 0, -1}, x8 = {0, 1, 1, 1, 0, -1, -1, -1}; vector y4 = {1, 0, -1, 0}, y8 = {1, 1, 0, -1, -1, -1, 0, 1}; template inline bool chmin(T& a, T b){if (a>b){a = b; return true;}return false;} template inline bool chmax(T& a, T b){if (a inline T powerM(T a,T b){if (b==0) return 1; T tmp = powerM(a,b/2); if (b%2==0) return tmp*tmp%MOD; else return tmp*tmp%MOD*a%MOD; } template inline T power(T a,T b,T m){ if (b==0) return 1; T tmp = power(a,b/2,m); if (b%2==0) return tmp*tmp%m; else return tmp*tmp%m*a%m; } template inline T gcd(T a, T b){if (b==0) return a; return gcd(b, a%b);} template inline T lcm(T a, T b){return a / gcd(a,b) * b;} // ax+by=gcd(a,b)を解く template inline T extgcd(T a,T b,T &x,T &y){if (b==0){x=1; y=0; return a;} T d=extgcd(b,a%b,y,x); y -= a/b*x; return d;} void hey(){ cout <<"hey" < struct edge { int to; T cost;}; // Dinic法:構造体-------------------------------------------- // 最大流問題に。O( |E||V|^2 ) だが非常に高速に動作することが多い // Dinic g(n); してからadd_edge(u, v, c) しまくり // 同じやつでverifyはした // 辺を表す構造体 {行き先, 容量, 逆辺} struct edgeflow {int to,cap,rev; }; struct Dinic { int V; vector> G; // グラフの隣接リスト表現 vector level; // sからの距離 vector iter; // どこまで調べ終わったか Dinic(int n) : G(n), level(n, -1), iter(n, 0) {} // fromからtoへ向かう容量capの辺をグラフに追加する void add_edge(int from, int to, int cap){ // 割と特殊なやり方をしてる G[from].push_back((edgeflow){to, cap, (int)G[to].size()}); G[to].push_back((edgeflow){from, 0, (int)G[from].size() - 1}); } // sからの最短距離をBFSで計算し、距離が増加する向きの辺のみからなるグラフを作成 void bfs(int s) { level.assign(level.size(), -1); queue que; level[s] = 0; que.push(s); while (!que.empty()) { int v = que.front(); que.pop(); for (int i=0; i 0 && level[e.to] < 0){ level[e.to] = level[v] + 1; que.push(e.to); } } } } // 増加パスをDFSで探す int dfs(int v, int t, int f) { if (v == t) return f; for (int &i=iter[v]; i 0 && level[v] < level[e.to]){ int d = dfs(e.to, t, min(f, e.cap)); if (d > 0){ e.cap -= d; // 使った分容量を減らす G[e.to][e.rev].cap += d; // 使った分逆辺の容量を増やす return d; } } } return 0; } // sからtへの最大流を求める int max_flow(int s, int t){ int flow = 0; while (true){ bfs(s); if (level[t] < 0) return flow; iter.assign(iter.size(), 0); int f; while ((f = dfs(s, t, INT_MAX/2)) > 0) flow += f; } } }; bool impossible(vector &field){ pair s, t; int H = field.size(), W = field[0].size(); rep(i, H){ rep(j, W){ if (field[i][j] == 'S') tie(s.first, s.second) = {i, j}; if (field[i][j] == 'T') tie(t.first, t.second) = {i, j}; }} if (s.first == t.first || s.second == t.second) return true; return false; } int main() { int P; cin >>P; // 最大流をP以上にできるか? int N1; cin >>N1; vector J(N1); rep(i, N1) cin >>J[i]; int N2; cin >>N2; vector C(N2); rep(i, N2) cin >>C[i]; vector> badmatch(N1, vector(N2, false)); rep(j, N2){ int q; cin >>q; rep(d, q){ int x; cin >>x; x--; badmatch[x][j] = true; } } // supersource: 0, genga: 1..N1, kantoku: N1+1..N1+N2, supersink: N1+N2+1 Dinic g(N1+N2+2); rep(i, N1) g.add_edge(0, i+1, J[i]); rep(i, N2) g.add_edge(N1+i+1, N1+N2+1, C[i]); rep(i, N1){ rep(j, N2){ int ii = i+1, jj = j+N1+1; if (badmatch[i][j]) continue; g.add_edge(ii, jj, 1000000000); } } int res = g.max_flow(0, N1+N2+1); cout <<(res >= P ? "SHIROBAKO" : "BANSAKUTSUKITA") <