P6938: 租赁服务

---

【题目描述】

【题目描述】
农民约翰意识到他从牛奶生产中获得的收入不足以为他农场的发展提供资金，所以为了赚点外快，他推出了一项奶牛租赁服务，他称之为“USACOW”(发音为“Use-a-cow”)。
农夫约翰有N头奶牛(1≤N≤100,000头)，每头奶牛每天能产一定数量的牛奶。FJ农场附近的M家店铺(1≤M≤100000)，每个店铺都会以一定的价格购买一定数量的牛奶。而且，农民约翰的R(1≤R≤100000)邻居农民都有兴趣以一定的价格租一头牛。
农夫约翰必须选择每头奶牛是挤奶还是租给附近的农民。帮助他找到他每天能赚到的最多的钱。
【输入格式】 (rent .in):
输入的第一行包含N、M和R，接下来的N行每一行包含一个整数ci(1≤ci≤1,000,000)，表示农夫John的第i头奶牛每天可以生产ci加仑的牛奶。接下来的M行每一行包含两个整数qi和pi(1≤qi,pi≤1,000,000)，表示第i家商店愿意以每加仑pi美分的价格购买最多qi加仑的牛奶。请记住，农民约翰可以向给定的商店出售0到qi加仑之间的任何数量的牛奶。接下来的R行每一行都包含一个整数ri(1≤ri≤1,000,000)，表示农夫约翰的一个邻居想以每天ri美分的价格租一头奶牛。
【输出格式】(rent .out):
输出应该包含一行，其中包含农民约翰每天通过挤奶或出租每头奶牛所能获得的最大利润。注意，输出可能太大，不适合标准的32位整数，因此您可能需要使用更大的整数类型，如C/ c++中的"long long"。
【样例输入】:
5 3 4
6
2
4
7
1
10 25
2 10
15 15
250
80
100
40
【样例输出】:
725
【样例说明】
农民约翰应该给1号和4号奶牛挤奶，以生产13加仑牛奶。他应该完全满足10加仑的订单，赚250美分，剩下的3加仑以每加仑15美分的价格出售，总共获得295美分的牛奶利润。
 
然后，他应该以250美分、80美分和100美分的价格出租其他三头牛，这样就可以多赚430美分。(他应该留下40美分租金的申请。)这总共是每天725美分的利润。

题目类型~

USACO-2018-银-1月 

咻咻~

提交答案 状态 返回