#include #include #include #define repeat(i,n) for (int i = 0; (i) < (n); ++(i)) typedef long long ll; using namespace std; ll maximum_flow(int s, int t, vector > const & g /* capacity, adjacency matrix */) { // edmonds karp, O(E^2V) int n = g.size(); vector > flow(n, vector(n)); auto residue = [&](int i, int j) { return g[i][j] - flow[i][j]; }; ll result = 0; while (true) { vector prev(n, -1); vector f(n); // find the shortest augmenting path queue q; // bfs q.push(s); while (not q.empty()) { int i = q.front(); q.pop(); repeat (j,n) if (prev[j] == -1 and j != s and residue(i,j) > 0) { prev[j] = i; f[j] = residue(i,j); if (i != s) f[j] = min(f[j], f[i]); q.push(j); } } if (prev[t] == -1) break; // not found // backtrack for (int i = t; prev[i] != -1; i = prev[i]) { int j = prev[i]; flow[j][i] += f[t]; flow[i][j] -= f[t]; } result += f[t]; } return result; } const ll INF = 1000000007; int main() { int n; cin >> n; ll a = 0; vector > g(2*n+2, vector(2*n+2)); repeat (i,n) { ll b, c; cin >> b >> c; a += b + c; g[2*n][ i] = b; g[ i][ n+i] = INF; g[n+i][2*n+1] = c; } int m; cin >> m; repeat (i,m) { int d, e; cin >> d >> e; g[d][n+e] = INF; } cout << a - maximum_flow(2*n, 2*n+1, g) << endl; return 0; }