#define REP(i,n) for(int i=0; i<(int)(n); i++) #include inline int getInt(){ int s; scanf("%d", &s); return s; } #include #include #include #include #include using namespace std; struct Edge{ int cap; // capacity int to; int rev; // reverse edge id Edge(){} Edge(int c, int t, int r) : cap(c), to(t), rev(r){} }; template // Edge type class Graph{ public: typedef std::vector > G; private: G g; public: Graph(int n) : g(G(n)) {} void addEdge(int from, int to, int cap){ g[from].push_back(E(cap, to, g[to].size())); g[to].push_back(E(0, from, g[from].size() - 1)); } void addEdge(int from, int to, int cap, int cost){ g[from].push_back(E(cap, to, cost, g[to].size())); g[to].push_back(E(0, from, -cost, g[from].size() - 1)); } G &getRowGraph(){ return g; } }; template class Dinic{ typedef typename Graph::G G; G &g; std::size_t n; // size of graph std::vector level; std::vector iter; // other utilities // search length of shortest path from s void bfs(int s){ std::queue que; level = std::vector(n, -1); level[s] = 0; que.push(s); while(!que.empty()){ int v = que.front(); que.pop(); for(int i = 0; i < (int)g[v].size(); i++){ E &e = g[v][i]; if(e.cap > 0 && level[e.to] < 0){ level[e.to] = level[v] + 1; que.push(e.to); } } } } // search path int dfs(int v, int t, int f){ if(v == t) return f; for(int &i = iter[v]; i < (int)g[v].size(); i++){ E &e = g[v][i]; if(e.cap > 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; } public: Dinic(Graph &graph) : g(graph.getRowGraph()){ n = g.size(); } // Max flow of the flow from s to t. int solve(int s, int t){ int flow = 0; while(true){ int f; bfs(s); if(level[t] < 0) return flow; iter = std::vector(n, 0); while((f = dfs(s, t, INT_MAX)) > 0){ flow += f; } } } }; template int dinic(Graph &g, int s, int d){ return Dinic(g).solve(s, d); } int main(){ const int w = getInt(); const int n = getInt(); vector j(n); REP(i,n) j[i] = getInt(); const int m = getInt(); vector c(m); REP(i,m) c[i] = getInt(); vector > x(m, vector(n)); REP(i,m){ const int q = getInt(); REP(k,q) x[i][getInt() - 1] = 1; } Graph g(n + m + 2); const int src = n + m; const int dst = n + m + 1; REP(i,n){ g.addEdge(src, i, j[i]); REP(k,m) if(!x[k][i]){ g.addEdge(i, n + k, j[i]); } } REP(i,m){ g.addEdge(n + i, dst, c[i]); } puts(dinic(g, src, dst) >= w ? "SHIROBAKO" : "BANSAKUTSUKITA"); return 0; }