Vials

Bajtazar is a chemist. He is running an experiment that produces remedy X, a mixture that solves every problem of humankind.

Bajtazar has $n$ vials numbered $1$ through $n$, and each vial holds a different liquid substance. Vial $i$ holds a whole number of grams of substance $i$. Producing remedy X takes a sequence of $m$ steps. One step pours the entire contents of one vial into another vial. Assume the vials are large enough and that no drop is spilled while pouring. The vial that was poured out goes on a shelf and is not used again during the experiment.

Some pairs of substances react with each other and form a compound that settles as sediment. In each such reaction $1$ gram of the first substance combines with $1$ gram of the second, and $2$ grams of sediment appear. The reaction runs until one of its substrates is used up. The sediment reacts with nothing and stays on the wall of the vial where it formed until the experiment ends. Some reactions run faster than others. If several substances end up in one solution at the same time, the reactions between pairs of substances happen in a fixed order that Bajtazar knows. After each step Bajtazar waits until the substances in the destination vial have finished reacting, and only then performs the next step.

Bajtazar wonders whether his sequence of steps is optimal. He wants to know how much of the substrates is wasted once every step is done. Find the total number of grams of sediment.

The first line contains three integers $n$, $m$, $k$ ($0 \le m < n \le 200000$, $0 \le k \le 500000$): the number of vials (which is also the number of distinct substances), the number of steps in the experiment, and the number of substance pairs that react and form sediment.

The second line contains $n$ integers $g_1, g_2, \dots, g_n$ ($1 \le g_i \le 10^9$), where $g_i$ is the initial number of grams of substance $i$ in vial $i$.

Each of the next $m$ lines describes one step, in order. The $i$-th of these lines contains two integers $a_i$, $b_i$ ($1 \le a_i, b_i \le n$, $a_i \ne b_i$), meaning that step $i$ pours the contents of vial $a_i$ into vial $b_i$. If a vial is poured out in some step, it does not appear in any later step.

Each of the next $k$ lines describes one pair of substances that forms sediment. The $i$-th of these lines contains two integers $c_i$, $d_i$ ($1 \le c_i, d_i \le n$, $c_i \ne d_i$), meaning that if substances $c_i$ and $d_i$ are in one vial at the same time, they react and sediment forms. The pairs are listed from the highest reaction priority to the lowest. If a vial holds two or more reacting pairs, the pair listed earlier in the input starts reacting first and finishes completely before the next pair starts. Ignoring the order inside a pair, the same pair $(c_i, d_i)$ never appears twice.

Print one integer, the total number of grams of sediment after the whole sequence of steps.