정복

유목민, 왕국, 부족들이 대해의 섬들에 자리 잡고 있다. 섬들 사이에는 다리가 놓여 있어 서로 오갈 수 있다. 어떤 섬에서든 일련의 다리를 거쳐 다른 모든 섬으로 이동할 수 있다. 섬들은 평화로웠지만, Spanning Nation이 공격하면서 모든 것이 바뀌었다!

처음에 Spanning Nation은 섬 1을 점령하고 있다. 그 시점부터 Spanning Nation은 이미 정복한 섬과 직접 연결된 어떤 섬이든 공격할 수 있다. 다행히 전쟁은 전투 없이 해결된다. Spanning Nation은 그 섬의 군대가 Spanning Nation의 군대보다 엄격히 작은 경우에만 섬을 공격한다. 그 섬의 더 작은 군대는 그저 항복하고 Spanning Nation의 군대에 합류한다.

Spanning Nation의 전술 고문으로서, 일련의 공격을 수행한 뒤 Spanning Nation이 가질 수 있는 최대 군대 규모를 구한다.

첫 번째 줄에는 섬의 수를 나타내는 정수 $N$ ($1 \leq N \leq 200\,000$)와 다리의 수를 나타내는 $M$ ($0 \leq M \leq 200\,000$)이 주어진다.

다음 $M$개의 줄에는 다리가 설명된다. 각 줄에는 서로 다른 두 정수 $u$와 $v$ ($1 \leq u, v \leq N$)가 주어지며, 이는 섬 $u$과 $v$ 사이에 다리가 있음을 나타낸다. 어떤 섬 쌍 사이에도 다리는 최대 하나만 존재한다.

다음 $N$개의 줄에는 섬들의 군대 규모가 순서대로 설명된다. 각 줄에는 정수 하나인 $s$ ($0 \leq s \leq 1\,000$)가 주어지며, 이는 해당 섬의 군대 규모이다.

Spanning Nation의 가능한 최대 군대 규모를 출력한다.