#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long int ll; typedef unsigned int uint; typedef unsigned char uchar; typedef unsigned long long ull; typedef pair pii; typedef pair pll; typedef vector vi; #define REP(i,x) for(int i=0;i<(int)(x);i++) #define REPS(i,x) for(int i=1;i<=(int)(x);i++) #define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--) #define RREPS(i,x) for(int i=((int)(x));i>0;i--) #define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++) #define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++) #define ALL(container) (container).begin(), (container).end() #define RALL(container) (container).rbegin(), (container).rend() #define SZ(container) ((int)container.size()) #define mp(a,b) make_pair(a, b) #define pb push_back #define eb emplace_back #define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() ); template bool chmax(T &a, const T &b) { if (a bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; } template ostream& operator<<(ostream &os, const vector &t) { os<<"["; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"]"; return os; } template ostream& operator<<(ostream &os, const set &t) { os<<"{"; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"}"; return os; } template ostream& operator<<(ostream &os, const pair &t) { return os<<"("< pair operator+(const pair &s, const pair &t){ return pair(s.first+t.first, s.second+t.second);} template pair operator-(const pair &s, const pair &t){ return pair(s.first-t.first, s.second-t.second);} typedef int Weight; const Weight INF=99999999; struct Edge{ int src,dst; Weight weight; int rev; Edge(int f, int t, Weight c,int rev=0):src(f),dst(t),weight(c),rev(rev){} }; struct Node:public vector{}; bool operator<(const Edge &a,const Edge &b){ return a.weight(const Edge &a,const Edge &b){return b Graph; typedef vector Array; typedef vector > Matrix; void add_edge(Graph &G,int s,int t,Weight cap){ G[s].push_back(Edge(s,t,cap,G[t].size())); G[t].push_back(Edge(t,s,0,G[s].size()-1)); } Weight dfs(const Graph &G, int v, int t, Weight f, const Matrix &cap, Matrix &flow, vector &visit){ visit[v]=true; if(v == t) return f; REP(i, G[v].size()){ const Edge &e = G[v][i]; Weight c = cap[v][e.dst] - flow[v][e.dst] + flow[e.dst][v]; if(!visit[e.dst] && c > 0){ Weight res = dfs(G, e.dst, t, min(f, c), cap, flow, visit); if(res > 0){ flow[v][e.dst] += res; return res; } } } return 0; } // 最大流を求める。 // Ford-Fulkerson // O(FE+V^2) Weight maximum_flow(const Graph &G, int s, int t){ int V = G.size(); Matrix cap(V, Array(V,0)); // 容量制限 Matrix flow(V, Array(V,0)); // 流れている量 vector visit(V); REP(i,G.size())REP(j,G[i].size()){ const Edge &e = G[i][j]; cap[e.src][e.dst] += e.weight; } Graph network(V); // 辺の候補を求める。(余計な辺を見ないため) REP(i,V)REP(j,i){ if(cap[i][j] + cap[j][i] > 0){ network[i].push_back(Edge(i,j,0)); network[j].push_back(Edge(j,i,0)); } } Weight res = 0,f; while((f = dfs(network, s, t, INF, cap, flow, visit)) > 0){ res+=f; visit = vector(V); } return res; } int n, m, l; int main(int argc, char *argv[]){ ios::sync_with_stdio(false); cin >> n >> m; vi d(m); REP(i, m) cin >> d[i]; cin >> l; vi e(l); REP(i, l) cin >> e[i]; Graph g(m+l+2); int s = m+l; int t = s+1; REP(i, m) add_edge(g, s, i, d[i]); REP(i, l) add_edge(g, m+i, t, e[i]); REP(i, l){ int q; cin >> q; set se; REP(j, q){ int x; cin >> x; se.insert(x-1); } REP(j, m)if(!se.count(j)){ add_edge(g, j, m+i, INF); } } // cout << (maximum_flow(g, s, t)) << endl; cout << (maximum_flow(g, s, t) >= n ? "SHIROBAKO" : "BANSAKUTSUKITA") << endl; return 0; }