Rental Service

Input

The first line contains three integers $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5), $m (1 \leq m \leq 1 0^{5})$ m~(1 \le m \le 10^5), and $r (1 \leq r \leq 1 0^{5})$ r~(1 \le r \le 10^5). Each of the next $n$ lines contains an integer $c_{i} (1 \leq c_{i} \leq 1 0^{6})$ c_i(1 \le c_i \le 10^6), indicating that Farmer John's $i$ -th cow can produce $c_{i}$ c_i gallons of milk every day. Each of the next $m$ lines contains two integers $q_{i}$ q_i and $p_{i} (1 \leq q_{i}, p_{i} \leq 1 0^{6})$ p_i~(1 \le q_i, p_i \le 10^6), indicating that the $i$ -th store is willing to buy up to $q_{i}$ q_i gallons of milk for $p_{i}$ p_i cents per gallon. Keep in mind that Farmer John can sell any amount of milk between zero and $q_{i}$ q_i gallons to a given store. Each of the next $r$ lines contains an integer $r_{i} (1 \leq r_{i} \leq 1 0^{6})$ r_i~(1 \le r_i \le 10^6), indicating that one of Farmer John's neighbors wants to rent a cow for $r_{i}$ r_i cents per day.

Output

Print one integer: the maximum profit Farmer John can make per day by milking or renting out each of his cows. Note that the answer might be too large to fit into a standard 32-bit integer, so you may need to use a larger integer type such as "long long" in C/C++.

Examples

Example 1

Loading

Note

Farmer John should milk cows $1$ and $4$ to produce $13$ gallons of milk. He should completely fill the order for $10$ gallons, earning $250$ cents, and sell the remaining three gallons at $15$ cents each, for a total of $295$ cents of milk profit.

Then he should rent out the other three cows for $250$ , $80$ , and $100$ cents to earn $430$ more cents. (He should leave the request for a $40$ -cent rental unfilled.) This gives a total of $725$ cents of daily profit.