Cow Rental Service

Farmer John decided that milk sales alone do not bring in enough money to grow his farm. To earn extra income he started a service that rents his cows out.

Farmer John has $N$ cows, and each cow produces a fixed amount of milk per day. There are $M$ stores near the farm, and each store buys milk up to a fixed amount at a fixed price per gallon. $R$ neighboring farmers each want to rent one cow for a day at a fixed price.

For every cow Farmer John picks one of two options: milk it, or rent it out to a neighbor. Find the largest amount of money he can make in one day.

The first line contains $N$, $M$, and $R$ ($1 \leq N \leq 100,000$, $1 \leq M \leq 100,000$, $1 \leq R \leq 100,000$).

Each of the next $N$ lines contains one integer $c_i$ ($1 \leq c_i \leq 1,000,000$), meaning that the $i$th cow produces $c_i$ gallons of milk per day.

Each of the next $M$ lines contains two integers $q_i$ and $p_i$ ($1 \leq q_i, p_i \leq 1,000,000$), meaning that the $i$th store buys up to $q_i$ gallons of milk at $p_i$ cents per gallon. Farmer John may sell any amount between $0$ and $q_i$ gallons to that store.

Each of the next $R$ lines contains one integer $r_i$ ($1 \leq r_i \leq 1,000,000$), meaning that one neighbor pays $r_i$ cents to rent one cow for a day.

Print one line with the largest daily profit Farmer John can make by milking or renting out each of his cows. The answer can exceed the range of a 32-bit integer, so use a 64-bit integer type.

In the first example Farmer John milks cow 1 and cow 4 and gets 13 gallons. He fills the order for 10 gallons and earns 250 cents, then sells the remaining 3 gallons at 15 cents per gallon, so milk brings in 295 cents. He rents the other three cows out for 250, 80, and 100 cents, which adds 430 cents. He turns down the 40-cent rental request. The daily profit is 725 cents in total.