Farmer John has N cows (1≤N≤100,000), each capable of producing some amount of milk every day. The MM stores near FJ's farm (1≤M≤100,000) each offer to buy a certain amount of milk at a certain price. Moreover, Farmer John's RR (1≤R≤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.
farmer john有N(1≤N≤100,000)头牛,他想赚跟多的钱,所以他准备买牛奶和出租牛。有M(1≤M≤100,000 )家商店想买牛奶,每家商店的进货价不同。有R(1≤R≤100,000 )户邻居想租牛,每户人家的租价不同。 问他最多能赚多少钱。
输入:输入的第1行包含n,m,r三个整数。紧接着的n行每一行有1个整数Ci (1≤Ci≤1,000,000),表示第i头牛产出Ci加仑奶。再下面的m行每行有两个整数Qi与Pi (1≤Qi,Pi≤1,000,000),表示第i个商店最多以Pi美分每加仑的价格购买Qi加仑牛奶。FJ可销售0~Qi加仑牛奶到一个商店。然后的r行每行有一个整数Ri,表示FJ的第i个邻居想以Ri(1≤Ri≤1,000,000 ), 的价格租一头牛。
输出:仅一行。表示一天最多获得多少钱。
注意:int类型不够大!!!
说明: FJ 需要挤一号和四号奶牛的奶,共可得牛奶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.