#include // c #include // io #include #include #include #include // container #include #include #include #include #include #include // other #include #include #include #include #include using namespace std; typedef long long ll; typedef unsigned long long ull; #define ALL(c) (begin(c)),(end(c)) #define REP(i,n) FOR(i,0,n) #define REPr(i,n) FORr(i,0,n) #define FOR(i,l,r) for(int i=(int)(l);i<(int)(r);++i) #define FORr(i,l,r) for(int i=(int)(r)-1;i>=(int)(l);--i) #define EACH(it,o) for(auto it = (o).begin(); it != (o).end(); ++it) #define IN(l,v,r) ((l)<=(v) && (v)<(r)) #define UNIQUE(v) v.erase(unique(ALL(v)),v.end()) //debug #define DUMP(x) cerr << #x << " = " << (x) #define LINE() cerr<< " (L" << __LINE__ << ")" class range { private: struct Iter{ int v; int operator*(){return v;} bool operator!=(Iter& itr) {return v < itr.v;} void operator++() {++v;} }; Iter i, n; public: range(int n) : i({0}), n({n}) {} range(int i, int n) : i({i}), n({n}) {} Iter& begin() {return i;} Iter& end() {return n;} }; //input template istream& operator >> (istream& is,pair& p){is>>p.first>>p.second;return is;} template istream& operator >> (istream& is,tuple& t){is >> get<0>(t);return is;} template istream& operator >> (istream& is,tuple& t){is >> get<0>(t) >> get<1>(t);return is;} template istream& operator >> (istream& is,tuple& t){is >>get<0>(t)>>get<1>(t)>>get<2>(t);return is;} template istream& operator >> (istream& is,tuple& t){is >> get<0>(t)>>get<1>(t)>>get<2>(t)>>get<3>(t);return is;} template istream& operator >> (istream& is, const tuple& t){is >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t) >> get<4>(t);return is;} template istream& operator >> (istream& is, const tuple& t){is >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t) >> get<4>(t) >> get<5>(t);return is;} template istream& operator >> (istream& is, const tuple& t){is >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t) >> get<4>(t) >> get<5>(t) >> get<6>(t);return is;} template istream& operator >> (istream& is,vector& as){REP(i,as.size())is >>as[i];return is;} //output template ostream& operator << (ostream& os, const set& ss){for(auto a:ss){if(a!=ss.begin())os<<" "; os< ostream& operator << (ostream& os, const pair& p){os< ostream& operator << (ostream& os, const map& m){bool isF=true;for(auto& p:m){if(!isF)os< ostream& operator << (ostream& os, const tuple& t){os << get<0>(t);return os;} template ostream& operator << (ostream& os, const tuple& t){os << get<0>(t)<<" "<(t);return os;} template ostream& operator << (ostream& os, const tuple& t){os << get<0>(t)<<" "<(t)<<" "<(t);return os;} template ostream& operator << (ostream& os, const tuple& t){os << get<0>(t)<<" "<(t)<<" "<(t)<<" "<(t);return os;} template ostream& operator << (ostream& os, const tuple& t){os << get<0>(t)<<" "<(t)<<" "<(t)<<" "<(t)<<" "<(t);return os;} template ostream& operator << (ostream& os, const tuple& t){os << get<0>(t)<<" "<(t)<<" "<(t)<<" "<(t)<<" "<(t)<<" "<(t);return os;} template ostream& operator << (ostream& os, const tuple& t){os << get<0>(t)<<" "<(t)<<" "<(t)<<" "<(t)<<" "<(t)<<" "<(t)<<" "<(t);return os;} template ostream& operator << (ostream& os, const vector& as){REP(i,as.size()){if(i!=0)os<<" "; os< ostream& operator << (ostream& os, const vector>& as){REP(i,as.size()){if(i!=0)os< T INF(){assert(false);}; template<> int INF(){return 1<<28;}; template<> ll INF(){return 1LL<<58;}; template<> double INF(){return 1e16;}; template<> long double INF(){return 1e16;}; template T EPS(){assert(false);}; template<> int EPS(){return 1;}; template<> ll EPS(){return 1LL;}; template<> double EPS(){return 1e-8;}; template<> long double EPS(){return 1e-8;}; template T pmod(T v,U M){return (v%M+M)%M;} class MaximamFlow{ private: typedef int Flow; struct Edge{int to;Flow icap,cap;}; typedef vector> Graph; //iter 次に調べる時の開始位置 距離 vector iter,dist; //sからのbfs距離 void bfs_dist(int s){ fill(ALL(dist),-1); dist[s]=0; queue que; que.push(s); while(!que.empty()){ int v=que.front();que.pop(); for(Edge& e:G[v])if(e.cap > 0 && dist[e.to] == -1){ dist[e.to]=dist[v]+1; que.push(e.to); } } } // s->t 増加パス Flow dfs_best_path(int s,int t,Flow f){ if(s==t)return f; for(int &i = iter[s];i < (int)G[s].size();i++){ Edge &e=G[s][i];Edge &reve = G[e.to][eid[e.to][s]]; if(e.cap <= 0 || dist[s]>=dist[e.to])continue; //search Flow d = dfs_best_path(e.to,t,min(f,e.cap)); if(d==0)continue; //found e.cap-=d;reve.cap+=d; return d; } return 0; } public: int V;Graph G; vector> eid; MaximamFlow(int V):V(V){ G=Graph(V); eid=vector>(V,vector(V,-1)); dist=vector(V,-1);iter=vector(V); } void add_edge(int s,int t,Flow cap){ if(eid[s][t]<0){eid[s][t]=G[s].size();G[s].push_back({t,0,0});} if(eid[t][s]<0){eid[t][s]=G[t].size();G[t].push_back({s,0,0});} G[s][eid[s][t]].icap=cap; G[s][eid[s][t]].cap=cap; } Flow change_cost(int S,int T,int s,int t,int c){ if(eid[s][t]<0)add_edge(s,t,c); Edge& e =G[s][eid[s][t]];Edge& reve = G[t][eid[t][s]]; Flow flow = 0; if(e.icap <= c){// 単純に増やす e.cap += c - e.icap; e.icap = c; }else if(c >= e.icap-e.cap){ // 単純に減らす e.cap -= e.icap - c; e.icap = c; }else{// フローを戻してから減らす Flow d = e.icap - e.cap - c; e.cap = 0;reve.cap = 0; //(1) S <- s <- t <- T のフローを戻す Flow fs = max_flow(s,S,d),ft = max_flow(T,t,d),f = min(fs,ft); max_flow(S,s,fs-f); max_flow(t,T,ft-f); flow -= f; //(2) (1)で戻せない分は t <- s <- t 内で無駄な t <- s 路ができているので除去する max_flow(s,t,d-f); e.cap = 0;reve.cap = c + reve.icap; e.icap = c; } flow+=max_flow(S,T); return flow; } int max_flow(int s,int t,Flow Mf=INF()){ if(s==t)return Mf; Flow flow=0; while(Mf>0){ bfs_dist(s); if(dist[t] == -1)break; Flow f; fill(ALL(iter),0); while((f=dfs_best_path(s,t,Mf))>0)flow+=f,Mf-=f; } return flow; } }; class Main{ public: void run(){ int W;cin >> W; int N;cin >> N; vector js(N);cin >> js; int M;cin >> M; vector cs(M);cin >> cs; MaximamFlow mf(N+M+2); int S=N+M,T=S+1; for(int i:range(M)){ int q;cin >> q; set xs; for(int j:range(q)){ int v;cin >> v;v--; xs.insert(v); } for(int j:range(N))if(!xs.count(j)){ mf.add_edge(j,N+i,INF()); } } for(int i:range(N))mf.add_edge(S,i,js[i]); for(int i:range(M))mf.add_edge(N+i,T,cs[i]); if(mf.max_flow(S, T)>=W){ cout <<"SHIROBAKO"<