P4181 [USACO18JAN] Rental Service S

题目描述

Farmer John 意识到牛奶生产的收入不足以支持农场的扩展，因此为了赚取额外收入，他推出了一项奶牛租赁服务，称为“USACOW”（发音为“Use-a-cow”）。

Farmer John 有 $N$ 头奶牛（$1 \leq N \leq 100,000$），每头奶牛每天可以生产一定量的牛奶。附近的 $M$ 家商店（$1 \leq M \leq 100,000$）每家都愿意以一定价格购买一定量的牛奶。此外，Farmer John 的 $R$ 个邻居（$1 \leq R \leq 100,000$）每家都愿意以一定价格租赁一头奶牛。

Farmer John 需要决定每头奶牛是用于产奶还是租给附近的农民。请帮助他计算每天可以赚取的最大金额。

输入格式

输入的第一行包含 $N$、$M$ 和 $R$。接下来的 $N$ 行每行包含一个整数 $c_i$（$1 \leq c_i \leq 1,000,000$），表示 Farmer John 的第 $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$ 到 $q_i$ 加仑。接下来的 $R$ 行每行包含一个整数 $r_i$（$1 \leq r_i \leq 1,000,000$），表示 Farmer John 的一个邻居愿意以每天 $r_i$ 美分的价格租赁一头奶牛。

输出格式

输出应包含一行，表示 Farmer John 通过产奶或租赁奶牛每天可以获得的最大利润。请注意，输出可能超过标准 32 位整数的范围，因此可能需要使用更大的整数类型，例如 C/C++ 中的 long long。

输入输出样例 1

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

725

说明/提示

Farmer John 应该让奶牛 #1 和 #4 产奶，每天生产 $13$ 加仑牛奶。他应该完全满足 $10$ 加仑的订单，赚取 $250$ 美分，并以每加仑 $15$ 美分的价格出售剩余的 $3$ 加仑，总共赚取 $295$ 美分的牛奶利润。

然后，他应该将其他三头奶牛分别以 $250$、$80$ 和 $100$ 美分的价格租出，赚取额外的 $430$ 美分。（他应该忽略 $40$ 美分的租赁请求。）这样，他每天的总利润为 $725$ 美分。