28283번 - 해킹

문제

네트워크 안에는 $N$개의 컴퓨터가 존재한다. 각 컴퓨터는 1,ドル 2, \cdots, N$번 컴퓨터로 번호가 붙어있다. 서로 다른 두 컴퓨터 쌍을 연결하는 $M$개의 통신망이 존재한다. $i$번째 통신망은 $S_i$번 컴퓨터와 $E_i$번 컴퓨터를 잇고 있다. 두 컴퓨터 쌍을 연결하는 통신망은 최대 하나 존재한다.

당신은 해커이다. $X$개의 컴퓨터를 동시에 해킹하여 돈을 얻고자 한다. $i$번 컴퓨터를 해킹하면, 1ドル$분 뒤부터 이 컴퓨터에서 매분 $A_i$만큼의 돈을 가져올 수 있다.

정부는 당신이 해킹하고 나서 0ドル.5$분 뒤 $B_1, B_2, \cdots, B_Y$번 컴퓨터에 보안 시스템을 설치할 계획이다. 당신이 해킹한 컴퓨터에 보안 시스템이 설치되고 나면 더 이상 이 컴퓨터에서 돈을 가져올 수 없다. 또한, 보안 시스템은 통신망을 통해 연쇄적으로 전파된다. 어떤 컴퓨터에 보안 시스템이 설치되고 나면, 1ドル$분 뒤 이 컴퓨터에서 통신망으로 직접 연결된 모든 컴퓨터에 보안 시스템이 자동으로 설치된다. 0ドル.5$분 뒤 보안 시스템이 설치될 예정인 컴퓨터를 해킹한다면 이 컴퓨터에서 돈을 가져올 수 없음에 유의하라.

정부의 계획을 알게 된 당신은 보안 시스템을 피해 최대한 많은 돈을 얻을 방법을 찾으려고 한다. 당신이 해킹한 컴퓨터들이 모두 보안 시스템에 의해 돈을 얻을 수 없게 되기 전까지 얼마나 많은 돈을 얻을 수 있는지 찾아보자.

입력

첫 번째 줄에 $N,ドル $M,ドル $X,ドル $Y$가 공백을 사이에 두고 주어진다.

두 번째 줄에는 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다.

세 번째 줄부터 $M$개의 줄에는 네트워크상의 통신망이 주어지는데, 이 중 $i(1 \leq i \leq M)$번째 줄에는 $S_i$와 $E_i$가 공백을 사이에 두고 주어진다.

다음 줄에는 $B_1, B_2, \cdots, B_Y$가 공백으로 구분되어 주어진다.

출력

최대로 얻을 수 있는 돈을 출력한다. 만약 무한히 많은 돈을 얻을 수 있다면 대신 $-1$을 출력한다.

제한

• 1ドル \leq N \leq 500,000円$
• 0ドル \leq M \leq 500,000円$
• 1ドル \leq X, Y \leq N$
• 0ドル \leq A_i \leq 500,000円$ (1ドル \leq i \leq N$)
• 1ドル \leq S_i, E_i \leq N, S_i ≠ E_i$ (1ドル \leq i \leq M$)
• $i \neq j$ 이면 $(S_i, E_i) ≠ (S_j, E_j), (S_i, E_i) ≠ (E_j, S_j)$
• 1ドル \leq B_i \leq N$ (1ドル \leq i \leq Y$)
• $i \neq j$ 이면 $B_i ≠ B_j$

힌트