Binary Robots

The hottest product on the robot market right now is the "binary robot". A binary robot is always designed so that it can perform two kinds of work (for example sewing and unstitching, or eating and philosophizing), but it can never do both at the same time. Rarely, because of a hardware fault, a robot is able to perform only a single kind of work.

Bajtazar runs a company that rents out binary robots. He owns $n$ robots; each robot $i$ has a fixed set of jobs it can perform and a rental price $w_i$. Bajtazar has received $m$ rental requests, each for a different job. When a robot is rented out it takes on exactly one of the jobs it is able to do, and each job (request) may be assigned to at most one robot. Bajtazar does not have to rent out every robot, nor accept every request.

Every robot that is rented out earns its rental price. Write a program that computes the maximum total revenue Bajtazar can earn.

The first line contains three integers $n$, $m$, $q$ ($1 \le n, m \le 1\,000\,000$, $0 \le q \le 2n$): the number of robots, the number of jobs (requests) to be done, and the total number of robot skills, respectively. Robots are numbered from $1$ to $n$ and jobs from $1$ to $m$.

The second line contains $n$ integers $w_1, w_2, \dots, w_n$ ($1 \le w_i \le 1\,000\,000\,000$), the rental price of each robot.

Each of the following $q$ lines contains two integers $a_i$, $b_i$ ($1 \le a_i \le n$, $1 \le b_i \le m$), meaning that robot $a_i$ can perform job $b_i$. No pair $(a_i, b_i)$ appears more than once. Moreover, for every $x = 1, 2, \dots, n$ a pair of the form $(x, y)$ appears exactly once or twice; that is, every robot can perform one or two jobs.

Print a single integer: the maximum total revenue Bajtazar can earn.