题目描述

Farmer John realizes that the income he receives from milk production is insufficient to fund the growth of his farm, so to earn some extra money, he launches a cow-rental service, which he calls "USACOW" (pronounced "Use-a-cow").

Farmer John has $N$ cows ($1 \leq N \leq 100,000$), each capable of producing some amount of milk every day. The $M$ stores near FJ's farm ($1 \leq M \leq 100,000$) each offer to buy a certain amount of milk at a certain price. Moreover, Farmer John's $R$ ($1 \leq R \leq 100,000$) neighboring farmers are each interested in renting a cow at a certain price.

Farmer John has to choose whether each cow should be milked or rented to a nearby farmer. Help him find the maximum amount of money he can make per day.

输入格式

The first line in the input contains $N$, $M$, and $R$. The next $N$ lines each contain an integer $c_i$ ($1 \leq c_i \leq 1,000,000$), indicating that Farmer John's $i$th cow can produce $c_i$ gallons of milk every day. The next $M$ lines each contain two integers $q_i$ and $p_i$ ($1 \leq q_i, p_i \leq 1,000,000$), indicating that the $i$th store is willing to buy up to $q_i$ gallons of milk for $p_i$ cents per gallon. Keep in mind that Farmer John can sell any amount of milk between zero and $q_i$ gallons to a given store. The next $R$ lines each contain an integer $r_i$ ($1 \leq r_i \leq 1,000,000$), indicating that one of Farmer John's neighbors wants to rent a cow for $r_i$ cents per day.

输出格式

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

题目大意

Farmer John 有 $N$ ($1 \leq N \leq 100,000$) 头牛，他想赚更多的钱，所以他准备买牛奶和出租牛。有 $M$ ($1 \leq M \leq 100,000$) 家商店想买牛奶，每家商店的进货价不同。有 $R$ ($1 \leq R \leq 100,000$) 户邻居想租牛，每户人家的租价不同。 问他最多能赚多少钱。

输入：输入的第 $1$ 行包含 $n$，$m$，$r$ 三个整数。紧接着的 $n$ 行每一行有1个整数 $C_i$ ($1 \leq C_i \leq 1,000,000$)，表示第 $i$ 头牛产出 $C_i$ 加仑奶。再下面的 $m$ 行每行有两个整数 $Q_i$ 与 $P_i$ ($1 \leq Q_i, P_i \leq 1,000,000$)，表示第 $i$ 个商店最多以 $P_i$ 美分每加仑的价格购买 $Q_i$ 加仑牛奶。Farmer John 可销售 $0 \sim Q_i$ 加仑牛奶到一个商店。接下来的 $r$ 行每行有一个整数 $R_i$，表示 Farmer John 的第 $i$ 个邻居想以 $R_i$ ($1 \leq R_i \leq 1,000,000$) 的价格租一头牛。

输出：仅一行。表示一天最多获得多少钱。

注意：int 类型不够大！！！

说明：Farmer John 需要挤一号和四号奶牛的奶，共可得牛奶 $13$ 加仑。他可以先买给出价最高的 $10$ 加仑，赚 $250$ 美分，然后把剩下的按每加仑 $15$ 美分去卖，共有 $295$ 美分的利润。 然后，他要把其他三头以 $250$, $80$ 和 $100$ 美分的价格分别卖出，赚 $430$ 美分。所以他一共可得 $725$ 美分/日的利润。

---by 风格雨关、WuYongxuan、毕沁露

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

725

提示

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 profits.

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 is a total of 725 cents of daily profit.