USACOW: Milk and Cow Rental Optimization

Farmer John owns N cows, each capable of producing a certain amount of milk per day. Nearby, M stores are willing to buy milk: each store will purchase up to a specified quantity of milk at a given price per unit. In addition, R neighboring farmers are interested in renting cows for a fixed daily price.

For each cow, Farmer John must decide whether to milk it (and then sell the milk to the stores) or rent it out. Note that if there are more cows than rental offers, only the top rental prices will be used, and the remaining cows must be milked.

Your task is to help him determine the maximum amount of money he can earn per day.

Input constraints:

• 1 \( \leq N \leq 100,000 \)
• 1 \( \leq M \leq 100,000 \)
• 1 \( \leq R \leq 100,000 \)

Note: Any formulas in the statement are given in LaTeX format.

inputFormat

The input begins with a line containing three space-separated integers: N, M, and R.

This is followed by N lines, each containing an integer representing the amount of milk produced by one cow.

Then follow M lines. Each of these lines contains two space-separated integers \(q\) and \(p\), where \(q\) is the maximum quantity of milk the store is willing to buy and \(p\) is the price per unit of milk (in dollars). The stores are not necessarily given in order of price.

Finally, there are R lines, each with a single integer representing the amount a neighboring farmer is willing to pay to rent one cow.

Example Input Format:

N M R
cow_1
cow_2
... (N lines total)
q1 p1
q2 p2
... (M lines total)
rental_1
rental_2
... (R lines total)

outputFormat

Output a single integer, which is the maximum amount of money Farmer John can make per day.

Output Example:

725

sample

5 3 4
7
6
4
2
1
10 25
15 15
2 10
250
80
100
40

725