Rental Service

题目描述

Farmer John 意识到他从牛奶生产中获得的收入不足以支持农场的发展，因此为了赚取额外收入，他推出了一项奶牛租赁服务，名为“USACOW”（读作“Use-a-cow”）。 Farmer John 有 $N$ 头奶牛（$1 \leq N \leq 100,000$），每头奶牛每天都能产出一定数量的牛奶。FJ 农场附近有 $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”。

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 美分，并将剩余的 3 加仑以每加仑 15 美分售出，从而获得总计 295 美分的牛奶收益。 然后，他应该将另外三头奶牛分别以 250、80 和 100 美分出租，额外赚取 430 美分。（他应当不满足 40 美分的租赁请求。）这样每天总利润为 725 美分。 题目贡献者：Jay Leeds

标签: USACO|2018|Silver

来源

USACO|2018|Silver