#include #define show(x) std::cerr << #x << " = " << (x) << std::endl template constexpr T INF = std::numeric_limits::max() / 10; class Flow { public: using T = int; struct Edge { std::size_t from, to, revind; T capacity, flow; bool reversed; }; Flow(const std::size_t v) : V{v}, edge(v) {} void addEdge(const std::size_t from, const std::size_t to, const T capacity) { edge[from].push_back(Edge{from, to, (std::size_t)edge[to].size(), capacity, 0, false}); edge[to].push_back(Edge{to, from, (std::size_t)edge[from].size() - 1, capacity, capacity, true}); } T FordFulkerson(const std::size_t s, const std::size_t t) { std::vector checked(V); auto dfs = [&](auto&& self, const std::size_t pos, const T& flow) -> T { if (pos == t) { return flow; } checked[pos] = true; for (auto& e : edge[pos]) { if (checked[e.to]) { continue; } const T res = e.capacity - e.flow; if (res <= 0) { continue; } const T d = self(self, e.to, std::min(flow, res)); if (d <= 0) { continue; } e.flow += std::min(d, res), edge[e.to][e.revind].flow -= std::min(d, res); return d; } return 0; }; T flow = 0; while (true) { fill(checked.begin(), checked.end(), false); const T f = dfs(dfs, s, INF); if (f == 0) { break; } flow += f; } return flow; } const std::size_t V; std::vector> edge; }; template std::ostream& operator<<(std::ostream& os, const std::vector& v) { os << "["; for (const auto& p : v) { os << p << ","; } return (os << "]\n"); } int main() { int W, N; std::cin >> W >> N; std::vector J(N); for (int i = 0; i < N; i++) { std::cin >> J[i]; } int M; std::cin >> M; std::vector C(M); for (int i = 0; i < M; i++) { std::cin >> C[i]; } std::vector> ok(N, std::vector(M, true)); for (int i = 0, Q; i < M; i++) { std::cin >> Q; for (int j = 0, X; j < Q; j++) { std::cin >> X, ok[Q - 1][i] = false; } } Flow f(N + M + 2); const int S = N + M, T = N + M + 1; for (int i = 0; i < N; i++) { f.addEdge(S, i, J[i]); } for (int i = 0; i < M; i++) { f.addEdge(N + i, T, C[i]); } for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (ok[i][j]) { f.addEdge(i, N + j, J[i]); } } } std::cout << (f.FordFulkerson(S, T) >= W ? "SHIROBAKO" : "BANSAKUTSUKITA") << std::endl; return 0; }