정복

시간 제한4초메모리 제한1024 MB

요약

1번 섬에서 시작해 인접한 섬 중 군대가 더 작은 섬을 흡수하며 병력을 합칠 때, 얻을 수 있는 최대 병력 총합을 구한다.

난이도: 보통10점 중 7점
유형: 그래프, 그리디, 힙, 유니온 파인드
정답자: 아직 제출이 없습니다

문제

큰 바다 위의 섬들에는 유목민, 왕국, 부족이 살고 있다. 섬들 사이에는 다리가 놓여 있어 서로 오갈 수 있다. 어떤 섬에서든 다리를 여러 번 건너면 다른 모든 섬에 도달할 수 있다. 섬들은 평화로웠지만, 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이 가질 수 있는 최대 군대 규모를 출력한다.

예제2

예제 1
입력
```
6 5
1 4
3 4
2 4
6 3
5 4
2
4
1
0
10
2
```
예상 출력
```
9
```
예제 2
입력
```
6 5
3 4
3 1
2 3
6 1
5 3
2
3
0
1
3
3
```
예상 출력
```
3
```