#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #pragma GCC optimize("Ofast") using namespace std; typedef long double ld; typedef long long int ll; typedef unsigned long long int ull; typedef vector vi; typedef vector vc; typedef vector vb; typedef vector vd; typedef vector vs; typedef vector vll; typedef vector > vpii; typedef vector > vvi; typedef vector > vvc; typedef vector > vvs; typedef vector > vvll; #define rep(i,n) for(int i = 0; i < (n); ++i) #define rrep(i,n) for(int i = 1; i <= (n); ++i) #define irep(it, stl) for(auto it = stl.begin(); it != stl.end(); it++) #define drep(i,n) for(int i = (n) - 1; i >= 0; --i) #define fin(ans) cout << (ans) << '\n' #define mp(p,q) make_pair(p, q) #define pb(n) push_back(n) #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define floatprec(dig) fixed << setprecision(dig) #define Sort(a) sort(a.begin(), a.end()) #define Rort(a) sort(a.rbegin(), a.rend()) #define MATHPI acos(-1) #define itn int; #define invar(typ, var) typ var; cin >> var; int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1}; int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1}; template inline bool chmax(T& a,T b){if(a inline bool chmin(T& a,T b){if(a>b){a=b;return 1;} return 0;} struct io{io(){ios::sync_with_stdio(false);cin.tie(0);}}; const int INF = INT_MAX; const ll LLINF = 1LL<<60; const ll MOD = 1000000007; const double EPS = 1e-9; //最大流問題 //頂点インデックスは0base //DINIC法 https://the-zeng.com/dinic/ class MaximumFlow { // 配列や構造の定義 struct edge {int to, cap, rev;}; int MV; vector > G; //メインのグラフ vector level; //BFSで使う vector iter; //DFSで使う //calculate min Distance from start with BFS void bfs(int s){ level.assign(MV, -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); } } } } //find path with DFS int dfs(int v, int t, int f){ if (v==t) return f; for (int &i = iter[v]; i < G[v].size() ; i++){ // &iは参照渡しかな edge &e = G[v][i]; if (e.cap > 0 && level[v] < level[e.to]){ //do not search for the edge which goes back 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; //DPRINT(e.to) } } } return 0; } public: MaximumFlow(int mv_) { MV = mv_; G.assign(MV, vector()); level.assign(MV, 0); iter.assign(MV, 0); } //add edge of cap which 'from -> to' void add_edge(int from, int to, int cap){ G[from].push_back((edge){to, cap, (int)(G[to].size()) }); G[to].push_back((edge){from, 0, (int)(G[from].size()) - 1 }); } int max_flow(int s, int t){ int flow = 0; for (;;){ //repeat eternally bfs(s); // edit 'level' if (level[t] < 0) return flow; // no route exist(finshed) iter.assign(MV, 0); //initiate iter[] int f; while ((f = dfs(s,t,INF)) > 0 ){ flow += f; } } } }; signed main(void) { cin.tie(0); ios::sync_with_stdio(false); invar(int, W); invar(int, N); vi genga(N); rep(i, N) cin >> genga[i]; invar(int, M); vi sakkan(M); rep(i, M) cin >> sakkan[i]; //頂点: //0 ~ N-1: 原画マン //N ~ N+M-1: 作監 //N+M: 起点 //N+M+1: 終点 MaximumFlow mf(N + M + 2); rep(i, N) { mf.add_edge(N+M, i, genga[i]); } rep(i, M) { mf.add_edge(N+i, N+M+1, sakkan[i]); } rep(i, M) { invar(int, Q); set bads; rep(_, Q) { //原画マン invar(int, X); --X; bads.emplace(X); } //Nごと rep(j, N) { if(bads.find(j) == bads.end()) { mf.add_edge(j, N+i, INF); } } } int res = mf.max_flow(N+M, N+M+1); fin(res < W ? "BANSAKUTSUKITA" : "SHIROBAKO"); }