#https://github.com/shakayami/ACL-for-python/wiki/maxflow #最大フロー問題 from collections import deque class mf_graph: n=1 g=[[] for i in range(1)] pos=[] def __init__(self,N): """初期化:Kはグラフの頂点数です。 初期化した直後は、頂点数Kで辺0のグラフとなります。""" self.n=N self.g=[[] for i in range(N)] self.pos=[] def add_edge(self,From,To,cap): """辺の追加:uからvへ、最大容量c,流量0の辺を追加します。""" assert 0<=From and Fromtoという辺を持っている。 最大流量capの辺にflowだけ辺が流れている という意味となっています。 """ m=len(self.pos) result=[] for i in range(m): result.append(self.get_edge(i)) return result def change_edge(self,i,new_cap,new_flow): m=len(self.pos) assert 0<=i and i0): v=que.popleft() for e in self.g[v]: if e["cap"]==0 or level[e["to"]]>=0:continue level[e["to"]]=level[v]+1 if e["to"]==t:return que.append(e["to"]) def dfs(func,v,up): if (v==s):return up res=0 level_v=level[v] for i in range(Iter[v],len(self.g[v])): e=self.g[v][i] if (level_v<=level[e["to"]] or self.g[e["to"]][e["rev"]]["cap"]==0):continue d=func(func,e["to"],min(up-res,self.g[e["to"]][e["rev"]]["cap"])) if d<=0:continue self.g[v][i]["cap"]+=d self.g[e["to"]][e["rev"]]["cap"]-=d res+=d if res==up:return res level[v]=self.n return res flow=0 while(flow0): p=que.popleft() visited[p]=True for e in self.g[p]: if e["cap"] and not(visited[e["to"]]): visited[e["to"]]=True que.append(e["to"]) return visited n = int(input()) mf = mf_graph(2*n+2) INF = 10**9 tot = 0 s = 2*n t = 2*n+1 for i in range(n): a,b = list(map(int, input().split())) mf.add_edge(s,2*i,b) mf.add_edge(2*i,2*i+1,a+b) mf.add_edge(2*i+1,t,a) tot += a+b m = int(input()) for i in range(m): d,e = list(map(int, input().split())) mf.add_edge(e*2+1,d*2,INF) ans = tot-mf.flow(s,t) print(ans)