#include using namespace std; using ll = long long; struct edge{ int to; ll cap; int rev; }; //Dinic(0-indexed) struct MaxFlow{ private: static const ll INF=9e18; vector dist, iter; vector> idx; void bfs(int s){ int from; fill(dist.begin(), dist.end(), -1); queue que; que.push(s); dist[s] = 0; while(!que.empty()){ from = que.front(); que.pop(); for (auto &e : E[from]){ if (e.cap > 0 && dist[e.to] == -1){ dist[e.to] = dist[from] + 1; que.push(e.to); } } } } ll dfs(int s, int t, ll flow){ if (s == t) return flow; for (int &i=iter[s]; i= dist[e.to]) continue; ll d = dfs(e.to, t, min(flow, e.cap)); if (d > 0){ e.cap -= d; E[e.to][e.rev].cap += d; return d; } } return 0; } public: int N, M=0; vector> E; MaxFlow(int n) : N(n) { E.resize(N); dist.resize(N); iter.resize(N); } void add_edge(int from, int to, ll cap){ M++; idx.push_back({from, (int)E[from].size()}); E[from].push_back({to, cap, (int)E[to].size()}); E[to].push_back({from, 0, (int)E[from].size()-1}); } ll solve(int s, int t, ll limit=INF){ ll res = 0, flow; while(1){ bfs(s); if (dist[t] == -1) break; for (int i=0; i 0){ res += flow; if (res >= limit) return limit; } } return res; } //i番目の辺の(from, to, flow)を求める。 tuple get_flow(int i){ assert (i < M); edge &e = E[idx[i].first][idx[i].second]; return {idx[i].first, e.to, E[e.to][e.rev].cap}; } //最小カット(s->t)を求める vector> get_cut(int s){ vector vst(N); vector> res; auto dfs=[&](auto self, int from)->void{ vst[from] = 1; for (auto &e : E[from]){ if (vst[e.to]) continue; if (e.cap) self(self, e.to); } }; dfs(dfs, s); for (int i=0; iDにコストBの辺 //C_1,..,C_Kのうち、1つでも使わない側に行けばBの損失 ll N, M, s=0, t, K, C, inf=1e18, ans=0; cin >> N >> M; MaxFlow mf(N+M+2); t = N+M+1; vector A(N+1), B(M+1); for (int i=1; i<=N; i++) cin >> A[i]; for (int i=1; i<=M; i++){ cin >> B[i]; ans += B[i]; } for (int i=1; i<=N; i++) mf.add_edge(i, t, A[i]); for (int i=1; i<=M; i++) mf.add_edge(s, i+N, B[i]); for (int i=1; i<=M; i++){ cin >> K; for (int j=0; j> C; mf.add_edge(i+N, C, inf); } } cout << ans-mf.solve(s, t) << endl; return 0; }