from collections import deque from math import inf from typing import List, Tuple, Union from dataclasses import dataclass import sys sys.setrecursionlimit(10**6) class MaxFlow: @dataclass class Edge: to: int rev: 'MaxFlow.Edge' cap: Union[int, float] def __init__(self, N: int): self.__N: int = N self.__G: List[List[MaxFlow.Edge]] = [[] for _ in range(N)] self.__E: List[Tuple[MaxFlow.Edge, MaxFlow.Edge]] = [] def add_edge(self, from_: int, to: int, capacity: Union[int, float]): assert 0 <= from_ < self.__N assert 0 <= to < self.__N assert 0 <= capacity from_edge = MaxFlow.Edge(to, None, capacity) to_edge = MaxFlow.Edge(from_, from_edge, 0) from_edge.rev = to_edge self.__E.append((from_edge, to_edge)) self.__G[from_].append(from_edge) self.__G[to].append(to_edge) return len(self.__E) - 1 def flow(self, source: int, sink: int, flow_limit: Union[int, float] = inf): assert 0 <= source < self.__N assert 0 <= sink < self.__N assert source != sink assert flow_limit >= 0 level: List[int] = [] cnt: List[int] = [] def bfs(): level[source] = 0 Q = deque([source]) while len(Q) != 0: u = Q.popleft() for edg in self.__G[u]: if edg.cap > 0 and level[edg.to] == -1: level[edg.to] = level[u] + 1 if edg.to == sink: return True Q.append(edg.to) return False def flow(e, f): if e == sink: return f while cnt[e] < len(self.__G[e]): edg = self.__G[e][cnt[e]] if edg.cap <= 0 or level[edg.to] <= level[e]: cnt[e] += 1 continue flowed = flow(edg.to, min(f, edg.cap)) if flowed > 0: edg.cap -= flowed edg.rev.cap += flowed return flowed level[e] = -1 return 0 answer = 0 while flow_limit > 0: level = [-1] * self.__N cnt = [0] * self.__N if not bfs(): break while True: flowed = flow(source, flow_limit) if flowed <= 0: break answer += flowed flow_limit -= flowed return answer def main(): N = int(input()) BC = [tuple(map(int, input().split())) for i in range(N)] M = int(input()) DE = [tuple(map(int, input().split())) for i in range(M)] G = MaxFlow(2*N+2) ans = 0 for i in range(N): B, C = BC[i] ans += max(B, C) G.add_edge(2*N, 2*i, max(B, C) - C) G.add_edge(2*i, 2*i+1, max(B, C)) G.add_edge(2*i+1, 2*N+1, max(B, C) - B) for d, e in DE: G.add_edge(2*d+1, 2*e, inf) ans -= G.flow(2*N, 2*N+1) print(ans) if __name__ == '__main__': main()