Neverland is a magical place consisting of several islands arranged in a circle. Each island is home to a unique species. However, all these species share a common behavioral trait: for any two creatures on the same island, there is exactly one common friend. That is, for any two creatures $a$ and $b$ on the same island, there is exactly one creature $c$ who is a friend of both $a$ and $b$. Of course, some islands may also have only one creature living in solitude. This trait has an obvious benefit: when two creatures have a conflict, they can ask that unique common friend to judge who is right and who is wrong.

In addition, there is communication between islands. Specifically, each island selects its smartest creature as a representative, and this representative becomes friends with the representatives of the two adjacent islands.

Unfortunately, World A is preparing to invade Neverland. As the guardian of Neverland, Lostmonkey wants to know the combat power of Neverland in a worst-case scenario. Since fighting side-by-side with friends increases one's ability, Lostmonkey wants to know the maximum combat power of Neverland without selecting any pair of friends. That is, select a set of creatures such that no two creatures in the set are friends, and the sum of their combat power is maximized.

Input

The first line contains two space-separated integers $n$ and $m$, representing the total number of creatures and the number of friend pairs in Neverland, respectively. The next $m$ lines describe all friend pairs; specifically, each line contains two space-separated integers $a$ and $b$, indicating that creature $a$ and creature $b$ are friends (each pair appears only once). The $(m+2)$-th line contains $n$ space-separated integers, where the $i$-th integer represents the combat power $A_i$ of creature $i$. The input data guarantees $4 \le n \le 100000$, $1 \le a,b \le n$, $1 \le m \le 200000$, and $-1000 \le A_i \le 1000$.

Output

Output a single integer representing the maximum combat power satisfying the condition.

Examples

Input 1

6 7
1 2
2 3
3 4
4 1
3 6
3 5
5 6
20 10 30 15 20 10

Output 1

50

Note

There are four islands. Creature 1 is on island 1, creature 2 is on island 2, creatures 3, 5, and 6 are on island 3, and creature 4 is on island 4.