Conquest

Time limit4sMemory limit1024 MB

Summary

Starting from island 1, absorb adjacent islands with strictly smaller armies, merging their sizes; maximize the final total army.

Level: Medium7 of 10
Topics: Graph, Greedy, Heap, Union-find
Solved: No attempts yet

Problem

Nomads, Kingdoms, and Tribes live on the islands of the great seas. Bridges span between islands, allowing travel between them. It is possible to get from every island to every other island through some sequence of bridges. The islands were at peace until everything changed when the Spanning Nation attacked.

Initially the Spanning Nation occupies island 1. From that point on, the Spanning Nation can attack any island that is directly connected to some island already conquered by the Spanning Nation. Wars are resolved without any fighting. The Spanning Nation only attacks an island if that island's army is strictly smaller than the Spanning Nation's army. The smaller island army simply concedes and joins the Spanning Nation's army.

As the tactical advisor of the Spanning Nation, determine the maximum possible army size the Spanning Nation can have after making a series of attacks.

Input

The first line contains the integer $N$ ( $1 \leq N \leq 200\,000$ ), the number of islands, and $M$ ( $0 \leq M \leq 200\,000$ ), the number of bridges.

The next $M$ lines describe the bridges. Each of these lines contains two distinct integers $u$ and $v$ ( $1 \leq u, v \leq N$ ), indicating that there is a bridge between islands $u$ and $v$ . There is at most one bridge between any pair of islands.

The next $N$ lines describe the islands' army sizes in order. Each of these lines contains a single integer $s$ ( $0 \leq s \leq 1\,000$ ), which is the army size of this island.

Output

Display the maximum possible army size of the Spanning Nation.

Examples2

Example 1
Input
```
6 5
1 4
3 4
2 4
6 3
5 4
2
4
1
0
10
2
```
Expected output
```
9
```
Example 2
Input
```
6 5
3 4
3 1
2 3
6 1
5 3
2
3
0
1
3
3
```
Expected output
```
3
```