#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define SOURCE 0 #define SINK 250 using namespace std; #define GRAPH_SIZE 251 struct edge{ int to, cap, rev; }; vector graph[GRAPH_SIZE]; bool used[GRAPH_SIZE]; void addedge( int from, int to, int cap ){ //枝を追加する。逆向きには容量0の真逆な枝を追加しておく。 graph[from].push_back( (edge){to,cap,(int)graph[to].size()} ); graph[to].push_back( (edge){from,0, (int)graph[from].size()-1} ); return; } int dfs( int v, int t, int f ){ if( v==t ) return f; used[v]=true; for( int i = 0 ; i < (int)graph[v].size(); i++){ edge &e = graph[v][i]; if( !used[e.to] && e.cap > 0 ){ int d = dfs(e.to, t, min(f,e.cap) ); if( d > 0 ){ e.cap -= d; graph[e.to][e.rev].cap += d; return d; } } } return 0; } int max_flow( int s, int t ){ int flow = 0; while(true){ memset(used, 0 , sizeof(used) ); int f = dfs(s,t,INT_MAX/2); if( f == 0 ) return flow; flow += f; } } int main(){ int N; cin >> N; int score[N+1][2]; int tot=0; for( int i = 1 ; i <= N ; i++){ cin >> score[i][0] >>score[i][1]; tot+=score[i][0]+score[i][1]; addedge(SOURCE,2*i,score[i][0]); addedge(2*i+1,SINK,score[i][1]); addedge(2*i,2*i+1,INT_MAX/2); } int M; cin >> M; for( int i=0;i>d>>e; addedge(2*d+2,2*e+3,INT_MAX/2); } cout << tot-max_flow(SOURCE,SINK); return 0; }