Maximum flow and matchings

Maximum Flow B

The bipartite graph, source and sink are given. Each disjoint set consists of n vertices. The edges with capacities ai run from the source to the vertices of the left set, from each vertex of the right set the edges of capacity bi run to the sink. The edges also run from the vertices of the left set to the vertices of the right set of infinite capacity. The current can flow in both directions along these edges. Find the value of maximum flow from source to the sink.


The numbers n and k (1n104, 0k105) are given - the number of vertices in each part of the graph and the number of edges between them. The second line contains the numbers ai (1ai104) - the edge capacities from source to each vertex in the left set. The third line contains the numbers bi (1bi104) - the edge capacities from each vertex of the right set to the sink. In each of the next k lines two numbers u and v (1u, vn) are given - the edge connects the vertex u of the left set and the vertex v of the right set.


Print the value of maximum flow.

Time limit 1 second
Memory limit 128 MiB
Input example #1
3 4
3 2 1
5 4 4
1 1
1 2
2 3
3 3
Output example #1
Source III International Summer School Programming in Sevastopol 2012