chessislands

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 Rm²), 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 Rm² 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 i^th 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 Rm² of black paint. We could also paint islands 2, 4 and 5 black, but this would not be minimal, as it uses 11 Rm² of black paint instead.