import std.stdio, std.array, std.string, std.conv, std.algorithm; import std.typecons, std.range, std.random, std.math, std.container; import std.numeric, std.bigint, core.bitop, std.bitmanip; void main() { immutable int INF = 1 << 29; auto N = readln.chomp.to!int; auto A = N.iota.map!(_ => readln.split.map!(to!int).array).array; auto M = readln.chomp.to!int; auto B = M.iota.map!(_ => readln.split.map!(to!int).array).array; int source = 2*N; int sink = 2*N+1; auto ff = new FordFulkerson(2*N+2, source, sink); foreach (i; 0..N) { ff.add_edge(source, i, A[i][0]); ff.add_edge(N+i, sink, A[i][1]); ff.add_edge(i, N+i, INF); } foreach (i; 0..M) { ff.add_edge(B[i][0], N+B[i][1], INF); } writeln(A.map!(a => a.sum).sum - ff.run); } class FordFulkerson { int N, source, sink; int[][] adj; int[][] flow; bool[] used; this(int n, int s, int t) { N = n; source = s; sink = t; assert (s >= 0 && s < N && t >= 0 && t < N); adj = new int[][](N); flow = new int[][](N, N); used = new bool[](N); } void add_edge(int from, int to, int cap) { adj[from] ~= to; adj[to] ~= from; flow[from][to] = cap; } int dfs(int v, int min_cap) { if (v == sink) return min_cap; if (used[v]) return 0; used[v] = true; foreach (to; adj[v]) { if (!used[to] && flow[v][to] > 0) { auto bottleneck = dfs(to, min(min_cap, flow[v][to])); if (bottleneck == 0) continue; flow[v][to] -= bottleneck; flow[to][v] += bottleneck; return bottleneck; } } return 0; } int run() { int ret = 0; while (true) { foreach (i; 0..N) used[i] = false; int f = dfs(source, int.max); if (f > 0) ret += f; else return ret; } } }