#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i)) #define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i)) #if defined(_MSC_VER) || __cplusplus > 199711L #define aut(r,v) auto r = (v) #else #define aut(r,v) __typeof(v) r = (v) #endif #define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it) #define all(o) (o).begin(), (o).end() #define pb(x) push_back(x) #define mp(x,y) make_pair((x),(y)) #define mset(m,v) memset(m,v,sizeof(m)) #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3fLL using namespace std; typedef vector vi; typedef pair pii; typedef vector > vpii; typedef long long ll; template inline void amin(T &x, U y) { if(y < x) x = y; } template inline void amax(T &x, U y) { if(x < y) x = y; } struct MaximumFlow { typedef int Index; typedef int Flow; static const Flow InfCapacity = INF; struct Edge { Index to; Flow capacity; Index rev; }; vector > g; void init(Index n) { g.assign(n, vector()); } void add(Index i, Index j, Flow capacity) { Edge e, f; e.to = j, f.to = i; e.capacity = capacity, f.capacity = 0; g[i].push_back(e); g[j].push_back(f); g[i].back().rev = (Index)g[j].size() - 1; g[j].back().rev = (Index)g[i].size() - 1; } void addB(Index i, Index j, Flow capacity) { Edge e, f; e.to = j, f.to = i; e.capacity = capacity, f.capacity = capacity; g[i].push_back(e); g[j].push_back(f); g[i].back().rev = (Index)g[j].size() - 1; g[j].back().rev = (Index)g[i].size() - 1; } //gを破壊する Flow maximumFlow(int s, int t) { int n = g.size(); vector level(n); Flow total = 0; bool update; do { update = false; fill(level.begin(), level.end(), -1); level[s] = 0; queue q; q.push(s); for(Index d = n; !q.empty() && level[q.front()] < d; ) { int u = q.front(); q.pop(); if(u == t) d = level[u]; each(e, g[u]) if(e->capacity > 0 && level[e->to] == -1) q.push(e->to), level[e->to] = level[u] + 1; } vector iter(n); for(Index i = 0; i < n; i ++) iter[i] = (int)g[i].size() - 1; while(1) { Flow f = augment(level, iter, s, t, InfCapacity); if(f == 0) break; total += f; update = true; } }while(update); return total; } Flow augment(vector &level, vector &iter, Index u, Index t, Flow f) { if(u == t || f == 0) return f; Index lv = level[u]; if(lv == -1) return 0; level[u] = -1; for(; iter[u] >= 0; -- iter[u]) { Edge &e = g[u][iter[u]]; if(level[e.to] <= lv) continue; Flow l = augment(level, iter, e.to, t, min(f, e.capacity)); if(l == 0) continue; e.capacity -= l; g[e.to][e.rev].capacity += l; level[u] = lv; return l; } return 0; } }; int main() { int N; while(~scanf("%d", &N)) { vector B(N); vector C(N); for(int i = 0; i < N; ++ i) scanf("%d%d", &B[i], &C[i]); int M; scanf("%d", &M); vector D(M); vector E(M); for(int i = 0; i < M; ++ i) scanf("%d%d", &D[i], &E[i]); MaximumFlow mf; int src = N * 2, dst = src + 1; mf.init(dst + 1); int sum = 0; rep(i, N) { //行かない: 0,1 あるいは 1,0 //行って、参加する: 1,1 //行って、参加しない: 0,0 //"行かない"に対応する状態が2つあることがポイントか mf.add(src, i, B[i]); mf.add(i, N + i, B[i] + C[i]); mf.add(N + i, dst, C[i]); sum += B[i] + C[i]; } rep(i, M) mf.add(N + D[i], E[i], INF); int f = mf.maximumFlow(src, dst); int ans = sum - f; printf("%d\n", ans); } return 0; }