#include #define rep(i,a,b) for(int i=a;i struct MaxFlow { struct edge { int to, reve; V cap; edge(int t, int r, V c) : to(t), reve(r), cap(c) {} }; int MV; vector> E; vector itr, lev; MaxFlow() {} MaxFlow(int n) { init(n); } void init(int n) { MV = n; itr = vector(MV), lev = vector(MV); E = vector>(MV); } void add_edge(int x, int y, V cap, bool undir = false) { E[x].push_back(edge(y, (int)E[y].size(), cap)); E[y].push_back(edge(x, (int)E[x].size() - 1, undir ? cap : 0)); } void bfs(int cur) { rep(i, 0, MV) lev[i] = -1; queue q; lev[cur] = 0; q.push(cur); while (q.size()) { int v = q.front(); q.pop(); for(auto e : E[v]) if (e.cap>0 && lev[e.to]<0) lev[e.to] = lev[v] + 1, q.push(e.to); } } V dfs(int from, int to, V cf) { if (from == to) return cf; for (; itr[from]cap>0 && lev[from]to]) { V f = dfs(e->to, to, min(cf, e->cap)); if (f>0) { e->cap -= f; E[e->to][e->reve].cap += f; return f; } } } return 0; } V maxflow(int from, int to) { V fl = 0, tf; while (1) { bfs(from); if (lev[to]<0) return fl; rep(i, 0, MV) itr[i] = 0; while ((tf = dfs(from, to, numeric_limits::max()))>0) fl += tf; } } }; /*---------------------------------------------------------------------------------------------------             ∧_∧       ∧_∧  (´<_` )  Welcome to My Coding Space      ( ´_ゝ`) /  ⌒i     /   \    | |     /   / ̄ ̄ ̄ ̄/  |   __(__ニつ/  _/ .| .|____      \/____/ (u ⊃ ---------------------------------------------------------------------------------------------------*/ #define INF 1e9 int N, B[50], C[50], M, D[5010], E[5010]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; MaxFlow mf(N * 2 + 2); int s = N * 2, t = N * 2 + 1; int sm = 0; rep(i, 0, N) { cin >> B[i] >> C[i]; int ma = max(B[i], C[i]); sm += ma; mf.add_edge(s, i, ma - C[i]); mf.add_edge(i, i + N, ma); mf.add_edge(i + N, t, ma - B[i]); } cin >> M; rep(i, 0, M) { cin >> D[i] >> E[i]; mf.add_edge(D[i], E[i] + N, INF); } cout << sm - mf.maxflow(s, t) << endl; }