#include #define ll long long #define INF 1000000005 #define MOD 1000000007 #define EPS 1e-10 #define rep(i,n) for(int i=0;i<(int)n;++i) #define each(a, b) for(auto (a): (b)) #define all(v) (v).begin(),(v).end() #define fi first #define se second #define pb push_back #define show(x) cout <<#x<<" = "<<(x)<P; const int MAX_N = 85; struct edge { int to,cap,rev; }; vector G[MAX_N]; int level[MAX_N]; int iter[MAX_N]; void add_edge(int from,int to,int cap) { G[from].push_back((edge){to,cap,G[to].size()}); G[to].push_back((edge){from,0,G[from].size()-1}); } void bfs(int s) { memset(level,-1,sizeof(level)); queue que; level[s] = 0; que.push(s); while(!que.empty()){ int v = que.front(); que.pop(); rep(i,G[v].size()){ edge &e = G[v][i]; if(e.cap > 0 && level[e.to] < 0){ level[e.to] = level[v] + 1; que.push(e.to); } } } } int dfs(int v,int t,int f) { if(v==t){ return f; } for(int &i = iter[v];i 0 && level[v] < level[e.to]){ int d = dfs(e.to,t,min(f,e.cap)); if(d>0){ e.cap -= d; G[e.to][e.rev].cap += d; return d; } } } return 0; } int max_flow(int s,int t) { int flow = 0; for(;;){ bfs(s); if(level[t]<0){ return flow; } memset(iter,0,sizeof(iter)); int f; while((f=dfs(s,t,INF)) > 0){ flow += f; } } } int main() { int n; cin >> n; vector b,c; int sm = 0; rep(i,n){ int x,y; cin >> x >> y; sm += x+y; b.pb(x),c.pb(y); } rep(i,n){ add_edge(0,i+1,b[i]); add_edge(n+i+1,2*n+1,c[i]); add_edge(i+1,n+i+1,INF); } int m; cin >> m; rep(i,m){ int x,y; cin >> x >> y; add_edge(x+1,n+y+1,INF); } cout << sm - max_flow(0,2*n+1) << endl; return 0; }