Bajtazar is a chemist. He is conducting an experiment to obtain "specimen X" — a mixture that solves all human problems.

Bajtazar has $n$ vials numbered from $1$ to $n$, containing various liquid substances. Vial $i$ contains an integer number of grams of substance $i$. To obtain specimen X, he must perform a sequence of $m$ steps. Each step consists of pouring the entire contents of one vial into another (we can assume that the vials have sufficiently large capacity and that not a single drop is spilled during the transfer). The vial from which the substance was poured is placed on a shelf and is not used in the remainder of the experiment.

For certain pairs of substances, it is known that they react with each other to form a chemical compound that precipitates as a sediment. For each such reaction, one gram of the first substance reacts with one gram of the second substance to produce two grams of sediment. The reaction continues until one of its substrates is exhausted. The precipitated sediment does not react with any substance and remains attached to the wall of the vial in which it was formed until the end of the experiment. Some reactions occur faster than others — if multiple substances are present in one solution at the same time, reactions between pairs of substances occur in a fixed order known to Bajtazar. After each step, Bajtazar waits for the substances in the target vial to react, and only then does he perform the next step.

Bajtazar wonders if the sequence of steps leading to the acquisition of specimen X is optimal. He would like to know how much of the substrates is wasted as a result of performing all the steps. He has asked you to help him find the total number of grams of precipitated sediment.

Input

The first line of input contains three integers $n$, $m$, and $k$ ($0 \le m < n \le 200\,000$, $0 \le k \le 500\,000$), representing, respectively: the number of vials (and thus the number of different substances), the length of the experiment's step sequence, and the number of pairs of substances that react with each other to form sediment.

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

The next $m$ lines contain the description of the sequence of steps leading to the acquisition of specimen X: the $i$-th of these lines contains two integers $a_i, b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$), meaning that the $i$-th step consists of pouring the contents of vial $a_i$ into vial $b_i$. It can be assumed that if the contents of a vial are poured in a certain step, that vial will not be used in any subsequent steps.

The next $k$ lines contain the description of pairs of substances that react with each other to form sediment: the $i$-th of these lines contains two integers $c_i, d_i$ ($1 \le c_i, d_i \le n, c_i \neq d_i$), meaning that if substances $c_i$ and $d_i$ are present in the same vial at the same time, a reaction will occur between them and sediment will precipitate. The pairs of substances are given in the order of their reaction priority, i.e., in the case where at least two pairs of reacting substances are present in a vial, the reaction of the pair given earliest in the input will begin (and finish completely) first. No unordered pair of numbers $(c_i, d_i)$ will repeat among these $k$ lines.

Output

The only line of output should contain a single integer representing the total number of grams of precipitated sediment after performing the entire sequence of experiment steps.

Examples

Input 1

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

Output 1

6