#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define sz size() #define pb push_back #define mp make_pair #define fi first #define se second #define all(c) (c).begin(), (c).end() #define rep(i,a,b) for(int i=(a);i<(b);++i) #define clr(a, b) memset((a), (b) ,sizeof(a)) #define MOD 1000000009 #define MAX_NODE 82 #define INF 100000000 namespace MF{ int nodes = MAX_NODE, src, dest; int dist[MAX_NODE], q[MAX_NODE], work[MAX_NODE]; struct Edge { int to, rev; int f, cap; }; vector g[MAX_NODE]; void ae(int s, int t, int cap){ Edge a = {t, g[t].size(), 0, cap}; Edge b = {s, g[s].size(), 0, cap}; g[s].push_back(a); g[t].push_back(b); } int dinic_bfs() { memset(dist, -1, sizeof(dist)); dist[src] = 0; int qt = 0; q[qt] = src; qt++; for(int i = 0; i < qt; i++) { int u = q[i]; for(int j = 0; j < (int)g[u].size(); j++){ Edge e = g[u][j]; int v = e.to; if(dist[v] < 0 && e.f < e.cap){ dist[v] = dist[u] + 1; q[qt] = v; qt++; } } } return dist[dest] >= 0 ? 1 : 0; } int dinic_dfs(int u, int f) { if(u == dest){ return f; } for(int i = work[u]; i < (int)g[u].size(); i++){ Edge &e = g[u][i]; if(e.cap <= e.f){ continue; } int v = e.to; if(dist[v] == dist[u]+1){ int df = dinic_dfs(v, min(f, e.cap - e.f)); if(df > 0){ e.f += df; g[v][e.rev].f -= df; return df; } } } return 0; } int maxFlowDinic(int _src, int _dest) { src = _src; dest = _dest; int result = 0; while(dinic_bfs() == 1){ memset(work, 0, sizeof(work)); for(;;){ int delta = dinic_dfs(src, INT_MAX); if(delta == 0)break; result += delta; } } return result; } } int main(){ int sum = 0; int n; cin >> n; rep(i,0,n){ int b,c; cin >> b >> c; MF::ae(2*n,i,b); MF::ae(i+n,2*n+1,c); MF::ae(i,i+n,INF); sum += b+c; } int m; cin >> m; rep(i,0,m){ int d,e; cin >> d >> e; MF::ae(d,e+n,INF); } int f = MF::maxFlowDinic(2*n,2*n+1); cout << sum-f << endl; return 0; } /* 最小カットの問題です。 最小カットとわかればやるだけな問題のはずです。 最小カットのなんたるかがよくわかっていないので、 シンプルに問題をまとめることができませんでした、 このようなややこしい条件ですいません。 */