/* Author:zeke pass System Test! GET AC!! */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using ll = long long; using ld = long double; using namespace std; #define rep(i, n) for(int i = 0; i < (int)(n); i++) #define all(x) (x).begin(),(x).end() #define rep3(var, min, max) for (ll (var) = (min); (var) < (max); ++(var)) #define repi3(var, min, max) for (ll (var) = (max) - 1; (var) + 1 > (min); --(var)) #define Mp(a,b) make_pair((a),(b)) #define F first #define S second #define CIN(s) int (s);cin>>(s); templatebool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (b P; typedef vector V; typedef vector VV; typedef vector

VP; ll MOD = 1e9 + 7; ll INF =1e18; //ここから template< typename flow_t > struct FordFulkerson { struct edge { int to; flow_t cap; int rev; bool isrev; int idx; }; vector< vector< edge > > graph; vector< int > used; const flow_t INF; int timestamp; FordFulkerson(int n) : INF(numeric_limits< flow_t >::max()), timestamp(0) { graph.resize(n); used.assign(n, -1); } void add_edge(int from, int to, flow_t cap, int idx = -1) { graph[from].emplace_back((edge) {to, cap, (int) graph[to].size(), false, idx}); graph[to].emplace_back((edge) {from, 0, (int) graph[from].size() - 1, true, idx}); } flow_t dfs(int idx, const int t, flow_t flow) { if(idx == t) return flow; used[idx] = timestamp; for(auto &e : graph[idx]) { if(e.cap > 0 && used[e.to] != timestamp) { flow_t d = dfs(e.to, t, min(flow, e.cap)); if(d > 0) { e.cap -= d; graph[e.to][e.rev].cap += d; return d; } } } return 0; } flow_t max_flow(int s, int t) { flow_t flow = 0; for(flow_t f; (f = dfs(s, t, INF)) > 0; timestamp++) { flow += f; } return flow; } void output() { for(int i = 0; i < graph.size(); i++) { for(auto &e : graph[i]) { if(e.isrev) continue; auto &rev_e = graph[e.to][e.rev]; cout << i << "->" << e.to << " (flow: " << rev_e.cap << "/" << e.cap + rev_e.cap << ")" << endl; } } } }; /*使い方: FordFulkerson(V):= 頂点数 Vで初期化する。 add_edge(from,to,cap):=頂点fromからtoに容量capの辺を張る。 max_flow(s,t,f):= 頂点sからtに最大流を流し、その流量を返す。 int main() { int V, E; scanf("%d %d", &V, &E); FordFulkerson< int > g(V); for(int i = 0; i < E; i++) { int a, b, c; scanf("%d %d %d", &a, &b, &c); g.add_edge(a, b, c); } printf("%d\n", g.max_flow(0, V - 1)); }*/ int main(){ ll w,n; cin>>w>>n; V J(n); rep(i,n)cin>>J[i]; ll m;cin>>m; V C(n); rep(i,m)cin>>C[i]; FordFulkerson g(2*n+2*m+100); rep(i,n)g.add_edge(0,i+1,1e18); rep(i,n)g.add_edge(i+1,i+n+1,J[i]); rep(i,m){ int q;cin>>q; vector have(100); rep(j,q){ int x;cin>>x; x--; have[x]=true; } rep(j,n){ if(have[j])continue; g.add_edge(j+n+1,2*n+i+1,1e18); } } rep(i,m)g.add_edge(2*n+1+i,2*n+m+1+i,C[i]); rep(i,m)g.add_edge(2*n+m+1+i,2*n+2*m+1,1e18); int k=g.max_flow(0,2*n+2*m+1); // cout<=w){ cout<<"SHIROBAKO"<