#include #include #include #include #include #include #include #include using namespace std; typedef int Weight; typedef int Capacity; struct Edge { int src, dst; Capacity cap; Edge(int s, int d, Capacity c) : src(s), dst(d), cap(c) {} }; typedef vector Edges; typedef vector Graph; struct Dinic { int n, s, t; vector level, prog, que; vector > cap, flow; vector > g; Capacity inf; Dinic() {} Dinic(const Graph &graph) : n(graph.size()), cap(n, vector(n)), flow(n, vector(n)), g(n, vector()), inf((int)1e9) { for(int i = 0; i < n; i++) { for(int j = 0; j < graph[i].size(); j++) { const Edge& e = graph[i][j]; int u = e.src, v = e.dst; Capacity c = e.cap; add_edge(u, v, c); } } } Dinic(int n_) : n(n_), cap(n, vector(n)), flow(n, vector(n)), g(n, vector()), inf((int)1e9) { } void add_edge(int u, int v, Capacity c) { cap[u][v] += c; cap[v][u] += c; flow[v][u] += c; g[u].push_back(v); g[v].push_back(u); } void reset() { for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { cap[i][j] = flow[i][j] = 0; } g[i].clear(); } } inline Capacity residue(int u, int v) { return cap[u][v] - flow[u][v]; } Capacity solve(int s_, int t_) { this->t = t_, this->s = s_; que.resize(n + 1); Capacity res = 0; while(levelize()) { prog.assign(n, 0); res += augment(s, inf); } return res; } bool levelize() { int l = 0, r = 0; level.assign(n, -1); level[s] = 0; que[r++] = s; while(l != r) { int v = que[l++]; if(v == t) break; for(int i = 0; i < g[v].size(); i++) { const int& d = g[v][i]; if(level[d] == -1 && residue(v, d) != 0) { level[d] = level[v] + 1; que[r++] = d; } } } return level[t] != -1; } Capacity augment(int v, Capacity lim) { Capacity res = 0; if(v == t) return lim; for(int &i = prog[v]; i < (int)g[v].size(); i++) { const int &d = g[v][i]; if(residue(v, d) == 0 || level[v] >= level[d]) continue; const Capacity aug = augment(d, min(lim, residue(v, d))); flow[v][d] += aug; flow[d][v] -= aug; res += aug; lim -= aug; if(lim == 0) break; } return res; } }; int main() { cin.tie(0); ios::sync_with_stdio(false); int N, M; cin >> N; Dinic dinic(2 * N + 2); int S = 2 * N, T = S + 1; int sum = 0; for(int i = 0; i < N; i++) { int b, c; cin >> b >> c; dinic.add_edge(S, i, b); dinic.add_edge(i, N + i, 10000000); dinic.add_edge(N + i, T, c); sum += b + c; } cin >> M; for(int i = 0; i < M; i++) { int d, e; cin >> d >> e; dinic.add_edge(N + d, e, 10000000); } cout << sum - dinic.solve(S, T) << endl; }