Ray the penguin has decided to repaint his extensive network of N icy islands (conveniently numbered 1..N) with a chess theme! Thus, he wishes to paint every island either black or white. Also, everyone knows that on a chessboard, white squares aren't next to white squares and black squares aren't next to black squares. Thus, in a similar vein, if two islands are connected by a bridge, one of them must be black and the other must be white. Also, since icy islands are already white (or at least, whitish), Ray only needs to buy some black paint now. Help him find the minimum amount of black paint he needs!
You are given the area of each island (in Ray-square-metres or Rm2), as well as a list of which islands are connected by bridges. It is guaranteed that there is a valid way to paint the islands such that no two connected islands have the same colour. Thus, output the minimum amount of area in Rm2 which needs to be painted black.
Note: Not all islands might be connected!
Input
On the first line are integers N and E, where E is the number of bridges. (1 ≤ N ≤ 50,000, 1 ≤ E ≤ 300,000)
The next N lines each contain one integer X, with the ith line representing the area of the island numbered i. (1 ≤ X ≤ 40,000).
The next E lines each contain two integers A and B, meaning that islands A and B are connected by a bridge.
Output
Output consists of a single line containing S, the minimum area which needs to be painted black.
Grading
For 50% of the test cases, all areas will be 1.
Sample Input 1
5 6
1
2
3
4
5
1 2
2 3
3 4
1 4
3 5
1 5
Sample Output 1
4
Explanation for Sample Output 1
By painting islands 1 and 3, we fulfill the given conditions and use 4 Rm2 of black paint. We could also paint islands 2, 4 and 5 black, but this would not be minimal, as it uses 11 Rm2 of black paint instead.