#include // clang-format off using namespace std; using ll=long long; using ull=unsigned long long; using pll=pair; const ll INF=4e18; void print0(){}; template void print0(H h,T... t){cout<void print1(H h,T... t){print0(h);if(sizeof...(T)>0)print0(" ");print1(t...);} void ioinit() { cout<> edgmap; vector edgs; vector route; vector level; vector searched_edge; int V; flow_dinic(int nodenum) { V = nodenum; edgmap.resize(V + 1); } void addedge(int u, int v, CAP cap) { int fwd_id = edgs.size(); int rev_id = edgs.size() + 1; edgs.push_back({fwd_id, v, cap, cap, rev_id}); edgs.push_back({rev_id, u, 0, 0, fwd_id}); edgmap[u].push_back(fwd_id); edgmap[v].push_back(rev_id); } CAP maxflow(int start, int goal) { // スタートに向かうダミーエッジを作る int fwd_id = edgs.size(); int rev_id = edgs.size() + 1; edgs.push_back({fwd_id, start, CAP_INF, CAP_INF, rev_id}); edgs.push_back({rev_id, V, 0, 0, fwd_id}); edgmap[V].push_back(fwd_id); edgmap[start].push_back(rev_id); const int level_inf = 1e9; while (true) { level.resize(0); level.resize(V + 1, level_inf); searched_edge.resize(0); searched_edge.resize(V + 1, 0); bfs(V); bool level_ok = false; while (true) { route.resize(0); CAP fmax = dfs(fwd_id, CAP_INF, goal); if (fmax >= 0) { level_ok = true; for (auto eid : route) { edgs[eid].cap -= fmax; edgs[edgs[eid].rev].cap += fmax; } } else { break; } } if (!level_ok) break; } CAP ans = edgs[fwd_id].orgcap - edgs[fwd_id].cap; // ダミーエッジ削除 edgmap[V].pop_back(); edgmap[start].pop_back(); edgs.pop_back(); edgs.pop_back(); return ans; } void bfs(int u0) { // startからの距離をlevelに入れる queue> q; q.push({u0, 0}); while (!q.empty()) { pair ul = q.front(); q.pop(); int u = ul.first; int lv = ul.second; if (level[u] <= lv) continue; level[u] = lv; for (auto neid : edgmap[u]) { if (edgs[neid].cap > 0) { // capが残っているedgeのみ利用 q.push({edgs[neid].v, lv + 1}); } } } } CAP dfs(int eid, CAP fmax, int goal) { route.push_back(eid); int u = edgs[eid].v; if (u == goal) { return fmax; } // searched_edge[u] -> ノードuについて、searched_edge[u] より小さいedgeは全て探索済みである while (searched_edge[u] < (int)edgmap[u].size()) { int neid = edgmap[u][searched_edge[u]]; int v = edgs[neid].v; if (level[u] < level[v] && edgs[neid].cap > 0) { // capが残っていて、levelが増えるedgeのみ利用 CAP nxt_fmax = min(fmax, edgs[neid].cap); CAP result = dfs(neid, nxt_fmax, goal); if (result >= 0) { return result; } } searched_edge[u]++; } route.pop_back(); return -1; } }; // 燃やす埋める問題とProject Selection Problemの整理 // https://qiita.com/tanaka-a/items/fb8d84c44190c7098047 class project_selection_problem { public: flow_dinic mf; vector ps; int start; int goal; project_selection_problem(int nodenum, int start_, int goal_) : mf(nodenum) { ps.resize(nodenum); start = start_; goal = goal_; } void add_profit(int u, CAP p) { // uを実施する場合、利得pを得る (pは負のこともありうる) ps[u] = p; if (p > 0) { mf.addedge(start, u, p); } else { mf.addedge(u, goal, -p); } } void add_rule(int x, int y, CAP z) { // x実施し、かつyを実施しない場合、損失zを得る (z>=0) mf.addedge(x, y, z); } CAP solve() { // 得られる最大の利得を求める CAP ans = 0; for (int i = 0; i < mf.V; i++) { ans += max(CAP(0), ps[i]); } ans -= mf.maxflow(start, goal); return ans; } }; // https://atcoder.jp/contests/abc225/tasks/abc225_g int h, w; int nodeid(int i, int j) { return i * w + j; } int main() { ioinit(); ll N, M; cin >> N >> M; vector A(N); for (ll i = 0; i < N; i++) { cin >> A[i]; } vector B(M); for (ll j = 0; j < M; j++) { cin >> B[j]; } vector> C(M, vector(N)); for (ll j = 0; j < M; j++) { ll k; cin >> k; for (ll x = 0; x < k; x++) { ll c; cin >> c; c--; C[j][c] = true; } } ll V = N + M + 2; ll start = V - 2; ll goal = V - 1; auto psp = project_selection_problem(V, start, goal); for (ll i = 0; i < N; i++) { psp.add_profit(i, -A[i]); } for (ll j = 0; j < M; j++) { psp.add_profit(j + N, B[j]); } for (ll i = 0; i < N; i++) { for (ll j = 0; j < M; j++) { if (C[j][i]) { psp.add_rule(j + N, i, CAP_INF); } } } print1(psp.solve()); }