#include #define rep(i,n) for(int i=0; i struct Flow { private: int n; vector> p; vector>> g; public: Flow(int n):n(n),g(n){} struct E { int u, v; C c, f; }; int add(int u, int v, C c) { int ui = int(g[u].size()); int vi = int(g[v].size()); if (u==v) ++vi; p.emplace_back(u,ui); g[u].emplace_back(v,vi,c); g[v].emplace_back(u,ui,0); return int(p.size()) - 1; } E getEdge(int i) { auto&[v,vi,cv] = g[p[i].first][p[i].second]; auto&[u,ui,cu] = g[v][vi]; return E{u, v, cu+cv, cu}; } void changeEdge(int i, C c, C f) { auto&[v,vi,cv] = g[p[i].first][p[i].second]; auto&[u,ui,cu] = g[v][vi]; cv = c - f; cu = f; } C flow(int s, int t, C flow = numeric_limits::max()) { vector depth(n); auto bfs = [&]{ fill(depth.begin(), depth.end(), -1); depth[s] = 0; queue q; q.push(s); while(q.size()){ int u = q.front(); q.pop(); for (auto [v,vi,c]:g[u]) { if (c==0 || depth[v]>=0) continue; depth[v] = depth[u]+1; if(v==t) return true; q.push(v); } } return false; }; function dfs = [&](int v, C up){ if(v==s) return up; C res = 0; for(auto&[u,ui,cu]:g[v]){ auto&[_,vi,cv] = g[u][ui]; if (depth[v]<=depth[u]||cv==0) continue; C f = dfs(u, min(up-res, cv)); if (f<=0) continue; cu += f; cv -= f; res += f; if (res == up) return res; } depth[v] = n; return res; }; C res = 0; while(flow && bfs()){ C f = dfs(t,flow); flow -= f; res += f; } return res; } vector cut(int s) { vector res(n); queue q; q.push(s); while (q.size()) { int u = q.front(); q.pop(); res[u] = true; for(auto&[v,vi,c]:g[u]){ if (c&&!res[v]) { res[v] = true; q.push(v); } } } return res; } }; int n,m,b,c,d,e; int f(int i,int j){ return i*2+j; } int main() { cin >> n; int s = n*2, t = s+1; Flow v(t+1); ll ans = 0; rep(i,n){ cin >> b >> c; ans += b+c; v.add(s,f(i,0),b); v.add(f(i,0),f(i,1),b+c); v.add(f(i,1),t,c); v.add(f(i,1),f(i,0),1e9); } cin >> m; rep(_,m){ cin >> d >> e; v.add(f(d,1),f(e,0),1e9); } ans -= v.flow(s,t); cout << ans << endl; }