시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB78524919930.757%

문제

네트워크 안에는 $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$

예제 입력 1

5 4 2 3
1 10 100 1000 10000
1 4
2 3
3 4
4 2
2 3 5

예제 출력 1

1002

예제 입력 2

3 0 1 1
1 0 0
2

예제 출력 2

-1

출처

University > 강원도 대학생 코딩 경진대회 > 강원도 대학생 코딩 경진대회 C번