#include #include #include #include #define repeat(i,n) for (int i = 0; (i) < (n); ++(i)) typedef long long ll; using namespace std; ll maximum_flow(int s, int t, vector > const & g /* capacity, adjacency matrix */) { // edmonds karp, O(E^2V) int n = g.size(); vector > flow(n, vector(n)); auto residue = [&](int i, int j) { return g[i][j] - flow[i][j]; }; ll result = 0; while (true) { vector prev(n, -1); vector f(n); // find the shortest augmenting path queue q; // bfs q.push(s); while (not q.empty()) { int i = q.front(); q.pop(); repeat (j,n) if (prev[j] == -1 and j != s and residue(i,j) > 0) { prev[j] = i; f[j] = residue(i,j); if (i != s) f[j] = min(f[j], f[i]); q.push(j); } } if (prev[t] == -1) break; // not found // backtrack for (int i = t; prev[i] != -1; i = prev[i]) { int j = prev[i]; flow[j][i] += f[t]; flow[i][j] -= f[t]; } result += f[t]; } return result; } int main() { // input int w, n; cin >> w >> n; vector j(n); repeat (i,n) cin >> j[i]; int m; cin >> m; vector c(m); repeat (i,m) cin >> c[i]; vector > x(m); repeat (i,m) { int q; cin >> q; repeat (j,q) { int y; cin >> y; x[i].insert(y-1); } } // make a capacity graph const ll INF = 1000000007; vector > g(n+m+2, vector(n+m+2)); int s = n+m, t = n+m+1; repeat (i,n) g[s][i] = j[i]; repeat (j,m) g[n+j][t] = c[j]; repeat (j,m) repeat (i,n) if (not x[j].count(i)) g[i][n+j] = INF; // output cout << (maximum_flow(s,t,g) >= w ? "SHIROBAKO" : "BANSAKUTSUKITA") << endl; return 0; }