package practice; 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); } FlowResolver fr = new BfsFlowResolver(graph); System.out.println(sum - fr.maxFlow(SOURCE, TARGET)); } interface Graph { void link(int from, int to, int cost); Optional getCost(int from, int to); int getVertexNum(); } interface FlowResolver { int maxFlow(int from, int to); } /** * グラフの行列による実装 * 接点数の大きいグラフで使うとMLEで死にそう */ 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; } } class BfsFlowResolver implements FlowResolver { private Graph graph; public BfsFlowResolver(Graph graph) { this.graph = graph; } public int maxFlow(int from, int to) { boolean finish = false; while (!finish) { Integer[] flows = new Integer[graph.getVertexNum()]; flows[from] = Integer.MAX_VALUE / 3; Integer[] froms = new Integer[graph.getVertexNum()]; boolean[] isPassed = new boolean[graph.getVertexNum()]; finish = false; while (!finish) { finish = true; for (int id = 0; id < graph.getVertexNum(); id++) { if (flows[id] != null) { if (flow(id, flows, froms)) { finish = false; } } } if (flows[to] != null) { int to_i = to; while (froms[to_i] != null) { graph.link(froms[to_i], to_i, graph.getCost(froms[to_i], to_i).get() - flows[to]); graph.link(to_i, froms[to_i], graph.getCost(to_i, froms[to_i]).orElse(0) + flows[to]); to_i = froms[to_i]; } finish = false; break; } } } int sum = 0; for (int id = 0; id < graph.getVertexNum(); id++) { sum += graph.getCost(to, id).orElse(0); } return sum; } public boolean flow(int from, Integer[] flows, Integer[] froms) { boolean change = false; for (int next = 0; next < graph.getVertexNum(); next++) { Optional cost = graph.getCost(from, next); if (cost.orElse(0) > 0 && flows[next] == null) { int nextFlow = flows[from] < cost.get() ? flows[from] : cost.get(); flows[next] = nextFlow; froms[next] = from; change = true; } } return change; } } /** * IDDFS(反復深化深さ優先探索)による実装 * 終了条件は同じ節点を2度通らないDFS(深さ優先探索)で0が返ってきたとき * ほぼDinic法なので計算量はO(E*V*V)のはず (E:辺の数, V:節点の数) */ class IddfsFlowResolver implements FlowResolver { private Graph graph; public IddfsFlowResolver(Graph graph) { this.graph = graph; } /** * 最大フロー(最小カット)を求める * @param from 始点(source)のID * @param to 終点(target)のID * @return 最大フロー(最小カット) */ public int maxFlow(int from, int to) { int sum = 0; int limitDepth = 0; while (isExistFlow(from, to)) { int currentFlow = flow(from, to,Integer.MAX_VALUE / 3, 0, limitDepth); sum += currentFlow; if (currentFlow == 0) { limitDepth++; } } return sum; } /** * フローの実行 グラフの更新も行う * @param from 現在いる節点のID * @param to 終点(target)のID * @param current_flow ここまでの流量 * @param depth 探索(ネスト)の深さ * @param limitDepth 深さ制限 * @return 終点(target)に流した流量/戻りのグラフの流量 */ private int flow(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(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; } /** * fromからtoに0以上の流量を流せるか調べる * @param from 始点(source)のID * @param to 終点(target)のID * @return 0以上流せればtrue */ private boolean isExistFlow(int from, int to) { boolean[] passed = new boolean[graph.getVertexNum()]; return search(from, to, passed); } /** * 今までに通ったことのない節点だけを調べるDFS(深さ優先探索) * 計算量は高々O(V)のはず (V:節点の数) * @param from 現在いる節点のID * @param to 終点(target)のID * @param passed 通過済みの節点IDにtrueが格納されている配列 * @return toに0以上流せればtrue */ private boolean search(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(id, to, passed)) { return true; } } return false; } } }