Maximum flow and matchings

Maximum Flow B

Time limit 1 second
Memory limit 128 MiB

The bipartite graph, source and sink are given. Each disjoint set consists of n vertices. The edges with capacities a[i] run from the source to the vertices of the left set, from each vertex of the right set the edges of capacity b[i] 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.

Input data

The numbers n and k (1n10^4, 0k10^5) 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 a[i] (1a[i]10^4) - the edge capacities from source to each vertex in the left set. The third line contains the numbers b[i] (1b[i]10^4) - 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.

Output data

Print the value of maximum flow.


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