길드에서 새로운 단원을 모으려고 한다.

사람마다 길드에 초대하는 데 필요한 비용이 다르다. 또한 서로 알고 있는 사람들끼리는 소문이 빠르게 퍼지기 때문에, 같은 친분 그룹에 속한 사람 중 한 명만 초대하면 그 그룹의 모든 사람이 길드에 들어온다.

친분 관계가 주어졌을 때, 모든 사람을 길드에 들어오게 하기 위해 필요한 최소 비용을 구하시오.

단, 사용할 수 있는 예산이 부족하다면 fail을 출력한다.

입력

첫째 줄에 사람의 수 \(N\), 친분 관계의 수 \(M\), 예산 \(K\)가 공백으로 구분되어 주어진다.

둘째 줄에 \(N\)개의 정수 \(C_1, C_2, \ldots, C_N\)이 공백으로 구분되어 주어진다. \(C_i\)는 \(i\)번 사람을 초대하는 데 필요한 비용이다.

다음 \(M\)개의 줄에는 서로 알고 있는 두 사람 \(a\), \(b\)가 공백으로 구분되어 주어진다.

같은 친분 관계가 여러 번 주어질 수 있다.

출력

모든 사람을 길드에 들어오게 하기 위해 필요한 최소 비용이 \(K\) 이하라면 그 최소 비용을 출력한다.

필요한 최소 비용이 \(K\)보다 크다면 fail을 출력한다.

제한 사항

• \(1 \le N \le 100,000\)

• \(0 \le M \le 100,000\)

• \(1 \le K \le 1,000,000,000,000\)

• \(1 \le C_i \le 1,000,000\)

• \(1 \le a, b \le N\)

• \(a \ne b\)

예제 설명 1

\(1\), \(2\), \(3\)번 사람은 같은 친분 그룹이고, 이 그룹에서는 \(3\)번 사람을 초대하는 비용 \(2\)가 가장 작다.

\(4\), \(5\)번 사람은 같은 친분 그룹이고, 이 그룹에서는 \(5\)번 사람을 초대하는 비용 \(4\)가 가장 작다.

따라서 필요한 최소 비용은 \(2 + 4 = 6\)이다.

First line \(N\), \(M\), \(K\); second line \(N\) costs \(C_i\); then \(M\) lines each with two acquaintances \(a\), \(b\) (\(1 \le N, M \le 10^5\), \(a \ne b\)).

Print the minimum total cost, or fail if it exceeds \(K\).

riseoj 작성

출처 Online Judge > GoldOJ