Hide

Problem G
Pool Pollution

Prince Peter’s Pool Park is a one of the most popular water parks in the world! The main attraction are the many pools (hence the name). To make cleaning easier many of the pools’ water systems are directly connected to each other via a series of pipes. Unfortunately, during a recent incident, a chemical spill occurred, spilling hazardous chemicals into some of the pools! Peter will have to shut down all the affected pools and all of the connected pools to be safe. Of course the more pools he shuts down the fewer people will be able to enjoy his park and thus the less profit he will be able to make. Peter has asked you to help him determine the number of people he will be able to accommodate if he shuts down the minimum number of pools.

Input

The first line of the input contains three integers $n$, $m$, and $k$ ($1 \leq n \leq 10^5$, $0 \leq m \leq 10^6$, and $1 \leq k \leq n$) where $n$ is the number of pools in the park, $m$ is the number of pipes connecting the pools, and $k$ is the number of pools that directly contaminated by the spill. The pools are numbered from $1$ to $n$. The next line contains $n$ integers $c_i$ ($1\leq c_i \leq 10^4$, $1\leq i \leq n$) where $c_i$ is the capacity of pool $i$. The next $m$ lines each contain two integers $a$ and $b$ ($1 \leq a, b \leq n$, $a \neq b$) indicating a pipe connecting pools $a$ and $b$. There may be multiple pipes connecting any two pools. Pipes are bidirectional, meaning that if either pool is contaminated then the other will be as well. The final line contains $k$ integers $p_i$ ($1 \leq p_i \leq n$, $1 \leq i \leq k$) indicating that pool $p_i$ has been directly contaminated by the chemical spill.

Output

Output a single integer, the maximum number of people that can be accommodated in the park if the minimum number of pools are shut down.

Sample Input 1 Sample Output 1
5 4 1
1 1 1 1 1
1 2
1 3
2 3
4 5
1
2
Sample Input 2 Sample Output 2
5 3 1
1 1 1 1 1
1 2
2 3
4 5
1
2
Sample Input 3 Sample Output 3
5 4 1
1 2 3 4 5
1 2
1 3
2 3
4 5
4
6
Sample Input 4 Sample Output 4
5 4 2
1 2 3 4 5
1 2
1 3
2 3
4 5
1 4
0

Please log in to submit a solution to this problem

Log in