#!/usr/bin/ python3.8 import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines from collections import deque class Dinic: def __init__(self, N, source, sink): self.N = N self.G = [[] for _ in range(N)] self.source = source self.sink = sink def add_edge(self, fr, to, cap): n1 = len(self.G[fr]) n2 = len(self.G[to]) self.G[fr].append([to, cap, n2]) self.G[to].append([fr, 0, n1]) # 逆辺を cap 0 で追加 def add_edge_undirected(self, fr, to, cap): n1 = len(self.G[fr]) n2 = len(self.G[to]) self.G[fr].append([to, cap, n2]) self.G[to].append([fr, cap, n1]) def bfs(self): level = [0] * self.N G = self.G source = self.source sink = self.sink q = deque([source]) level[source] = 1 pop = q.popleft append = q.append while q: v = pop() lv = level[v] + 1 for to, cap, rev in G[v]: if not cap: continue if level[to]: continue level[to] = lv if to == sink: self.level = level return append(to) self.level = level def dfs(self): INF = 10**18 G = self.G sink = self.sink prog = self.progress level = self.level ascend = False ff = 0 stack = [(self.source, INF)] while stack: if ff: # このまま更新だけして戻っていく v, f = stack.pop() p = prog[v] to, cap, rev = G[v][p] G[v][p][1] -= ff G[to][rev][1] += ff continue v, f = stack[-1] if v == sink: ff = f stack.pop() continue E = G[v] lv = level[v] if ascend: # 流せずに戻ってきた prog[v] += 1 find_flag = False for i in range(prog[v], len(E)): to, cap, rev = E[i] prog[v] = i if not cap: continue if level[to] <= lv: continue find_flag = True break if not find_flag: ascend = True stack.pop() continue ascend = False x = f if f < cap else cap stack.append((to, x)) return ff def max_flow(self): flow = 0 while True: self.bfs() if not self.level[self.sink]: return flow self.progress = [0] * self.N while True: f = self.dfs() if not f: break flow += f return flow N = int(readline()) source = N + N sink = N + N + 1 dinic = Dinic(N + N + 2, source, sink) X = 100 INF = 10 ** 9 add = dinic.add_edge for i in range(N): B, C = map(int, readline().split()) add(source, i, X - C) add(i, i + N, X) add(i + N, sink, X - B) add(i + N, i, INF) M = int(readline()) m = map(int, read().split()) for D, E in zip(m, m): add(D + N, E, INF) f = dinic.max_flow() answer = X * N - f print(answer)