Description

The chemist Gili wants to make a magical potion to save the world.

Gili has $n$ different liquid substances and $n$ bottles (both numbered from $1$ to $n$). Initially, bottle $i$ contains $g_i$ grams of substance $i$.

Gili needs to perform several steps to make the potion. In step $i$, she pours all the liquid from bottle $a_i$ into bottle $b_i$. After that, bottle $a_i$ will no longer be used. You may assume the bottles have unlimited capacity.

Gili knows that some pairs of substances will react together and produce precipitate. The reaction is: $1$ gram of substance $c_i$ and $1$ gram of substance $d_i$ produce $2$ grams of precipitate, and the reaction continues until one reactant is exhausted. The precipitate produced will not react with any substance.

When there is more than one pair of substances that can react in the same bottle, Gili knows the order in which they react. After each pouring, Gili waits until all reactions finish before performing the next step.

Gili wants to know the total amount of precipitate produced during the whole process.

Input Format

The first line contains three integers $n,m,k$, representing the number of bottles (i.e. the number of substances), the number of steps, and the number of possible reactions.

The second line contains $n$ integers $g_1,g_2,\dots,g_n$, representing the initial mass of the substance in each bottle.

The next $m$ lines each contain two integers $a_i,b_i$, representing step $i$. It is guaranteed that $a_i$ will not appear in any later step.

The next $k$ lines each contain a pair of substances $c_i,d_i$ that can react, given in the priority order of reactions. The same reaction will not appear more than once.

Output Format

Output the total mass of precipitate produced.

3 2 1
2 3 4
1 2
3 2
2 3

6

Hint

For $100\%$ of the testdata, $0 \le m < n \le 2 \times 10^5$, $0 \le k \le 5 \times 10^5$, $1 \le g_i \le 10^9$, $1 \le a_i,b_i,c_i,d_i \le n$, $a_i \ne b_i$, $c_i \ne d_i$.

Translated by ChatGPT 5