from collections import deque from math import inf import sys sys.setrecursionlimit(10**6) class MaxFlow: def __init__(self, N: int): self.__N = N self.__G = [[] for _ in range(N)] self.__E = [] def add_edge(self, from_: int, to: int, cap: int) -> int: """ Adds an edge oriented from vertex from_ to vertex to with capacity cap. Returns edge index. """ assert 0 <= from_ < self.__N assert 0 <= to < self.__N assert 0 <= cap from_edge = [to, None, cap] to_edge = [from_, from_edge, 0] from_edge[1] = 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 get_edge(self, i: int): """ Returns i-th edge state as tuple (from_, to, cap, flow) """ (to, _, flow), (from_, _, remain) = self.__E[i] return (from_, to, flow+remain, flow) def flow(self, source: int, sink: int, flow_limit: int = inf) -> float: """ Returns maximum-flow from vertex source to vertex sink, bounded with flow_limit. """ assert 0 <= source < self.__N assert 0 <= sink < self.__N assert source != sink assert flow_limit >= 0 level = [] cnt = [] def bfs(): level[source] = 0 Q = deque([source]) while len(Q) != 0: u = Q.popleft() for edg in self.__G[u]: to, _, cap = edg if cap > 0 and level[to] == -1: level[to] = level[u] + 1 if to == sink: return True Q.append(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]] to, rev, cap = edg if cap <= 0 or level[to] <= level[e]: cnt[e] += 1 continue flowed = flow(to, min(f, cap)) if flowed > 0: edg[2] -= flowed rev[2] += 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()