游牧民族、王国和部落居住在伟大海洋的岛屿上。岛屿之间由桥梁连接，允许往来通行。通过一系列桥梁，可以从任意一个岛屿到达其他任何岛屿。这些岛屿原本处于和平状态，直到“生成国”（Spanning Nation）发动了攻击，一切都改变了！

最初，“生成国”占领了岛屿 1。从那时起，“生成国”可以攻击任何与已征服岛屿直接相连的岛屿。幸运的是，战争无需战斗即可解决。“生成国”仅在目标岛屿的军队规模严格小于“生成国”自身军队规模时才会发起攻击。被征服岛屿的军队将直接投降并加入“生成国”的军队。

作为“生成国”的战术顾问，请确定在进行一系列攻击后，“生成国”可能拥有的最大军队规模。

输入格式

第一行包含整数 $N$ ($1 \le N \le 200\,000$)，表示岛屿的数量；以及 $M$ ($0 \le M \le 200\,000$)，表示桥梁的数量。

接下来的 $M$ 行描述了桥梁。每行包含两个不同的整数 $u$ 和 $v$ ($1 \le u, v \le N$)，表示岛屿 $u$ 和 $v$ 之间有一座桥。任意两个岛屿之间最多只有一座桥。

接下来的 $N$ 行按顺序描述了各岛屿的军队规模。每行包含一个整数 $s$ ($0 \le s \le 1\,000$)，表示该岛屿的军队规模。

输出格式

输出“生成国”可能拥有的最大军队规模。

样例

样例输入 1

6 5
1 4
3 4
2 4
6 3
5 4
2
4
1
0
10
2

样例输出 1

9

样例输入 2

6 5
3 4
3 1
2 3
6 1
5 3
2
3
0
1
3
3

样例输出 2

3