Neverland 是个神奇的地方，它由一些岛屿环形排列组成，每个岛上都生活着一种与众不同的物种。但这些物种都有一个共同的生活习性：对于同一岛上的任意两个生物，他们有且仅有一个公共朋友，即对于同一岛上的任意两个生物 a 和 b，有且仅有一个生物 c 既是 a 的朋友也是 b 的朋友。当然某些岛上也可能只有一个生物孤独地生活着。这一习性有一个明显的好处，当两个生物发生矛盾时，他们可以请那个唯一的公共朋友来裁决谁对谁错。

另外，岛与岛之间也有交流，具体来说，每个岛都会选出一个最聪明的生物做代表，然后这个生物与他相邻的两个岛的代表成为朋友。

不幸的是，A 世界准备入侵 Neverland，作为 Neverland 的守护者，Lostmonkey 想知道在一种比较坏的情况下 Neverland 的战斗力。因为和朋友并肩作战，能力会得到提升，所以 Lostmonkey 想知道在不选出一对朋友的情况下 Neverland 的最大战斗力。即选出一些生物，且没有一对生物是朋友，并要求它们的战斗力之和最大。

输入格式

第一行包含用空格隔开的两个整数 n 和 m，分别表示 Neverland 的生物总数和朋友对数。接下来的 m 行描述所有的朋友对，具体来说，每行包含用空格隔开的两个整数 a 和 b，表示生物 a 和生物 b 是朋友（每对朋友只出现一次）。第 m+2 行包含用空格隔开的 n 个整数，其中的第 i 个整数表示生物 i 的战斗力 $A_i$。输入的数据保证 $4 \le n \le 100000$，$1 \le a,b \le n$，$1 \le m \le 200000$，$-1000 \le A_i \le 1000$。

输出格式

输出仅包含一个整数，表示满足条件的最大战斗力。

样例数据

input.txt

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

output.txt

50

样例说明

有四个岛，生物 1 在 1 号岛，生物 2 在 2 号岛，生物 3、5、6 在 3 号岛，生物 4 在 4 号岛。