import java.util.Optional; import java.util.Scanner; public class Main { public static void main(String[] args) { Main main = new Main(); main.solveB(); } private void solveB() { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[] B = new int[N]; int[] C = new int[N]; for (int i = 0; i < N; i++) { B[i] = sc.nextInt(); C[i] = sc.nextInt(); } int M = sc.nextInt(); int[] D = new int[M]; int[] E = new int[M]; for (int i = 0; i < M; i++) { D[i] = sc.nextInt(); E[i] = sc.nextInt(); } final int VERTEX_NUM = 2 * N + 2; final int SOURCE = 0; final int TARGET = VERTEX_NUM - 1; int sum = 0; Graph graph = new ArrayGraph(VERTEX_NUM); for (int i = 0; i < N; i++) { graph.link(SOURCE, i+1, B[i]); graph.link(i+1, N+i+1, B[i] + C[i]); graph.link(N+i+1, TARGET, C[i]); sum += B[i] + C[i]; } for (int i = 0; i < M; i++) { graph.link(N+1+D[i], 1+E[i], Integer.MAX_VALUE / 3); } System.out.println(sum - maxFlow(graph, SOURCE, TARGET)); } interface Graph { void link(int from, int to, int cost); Optional getCost(int from, int to); int getVertexNum(); } class ArrayGraph implements Graph { private Integer[][] costArray; private int vertexNum; public ArrayGraph(int n) { costArray = new Integer[n][]; for (int i = 0; i < n; i++) { costArray[i] = new Integer[n]; } vertexNum = n; } @Override public void link(int from, int to, int cost) { costArray[from][to] = new Integer(cost); } @Override public Optional getCost(int from, int to) { return Optional.ofNullable(costArray[from][to]); } @Override public int getVertexNum() { return vertexNum; } } private int maxFlow(Graph graph, int from, int to) { int sum = 0; int limitDepth = 0; while (isExistFlow(graph, from, to)) { int currentFlow = flow(graph, from, to,Integer.MAX_VALUE / 3, 0, limitDepth); sum += currentFlow; if (currentFlow == 0) { limitDepth++; } } return sum; } private int flow(Graph graph, int from, int to, int current_flow, int depth, int limitDepth) { if (from == to) { return current_flow; } if (depth >= limitDepth) { return 0; } for (int id = 0; id < graph.getVertexNum(); id++) { Optional cost = graph.getCost(from, id); if (cost.orElse(0) > 0) { int nextFlow = current_flow < cost.get() ? current_flow : cost.get(); int returnFlow = flow(graph, id, to, nextFlow, depth+1, limitDepth); if (returnFlow > 0) { graph.link(from, id, cost.get() - returnFlow); graph.link(id, from, graph.getCost(id, from).orElse(0) + returnFlow); return returnFlow; } } } return 0; } private boolean isExistFlow(Graph graph, int from, int to) { boolean[] passed = new boolean[graph.getVertexNum()]; return search(graph, from, to, passed); } private boolean search(Graph graph, int from, int to, boolean[] passed) { if (from == to) { return true; } passed[from] = true; for (int id = 0; id < graph.getVertexNum(); id++) { if (!passed[id] && graph.getCost(from, id).orElse(0) > 0 && search(graph, id, to, passed)) { return true; } } return false; } }