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 需要决定每头奶牛是用于产奶还是租给附近的农民。请帮助他计算每天可以赚取的最大金额。

无

无

Farmer John 应该让奶牛 #1 和 #4 产奶，每天生产 $13$ 加仑牛奶。他应该完全满足 $10$ 加仑的订单，赚取 $250$ 美分，并以每加仑 $15$ 美分的价格出售剩余的 $3$ 加仑，总共赚取 $295$ 美分的牛奶利润。 然后，他应该将其他三头奶牛分别以 $250$、$80$ 和 $100$ 美分的价格租出，赚取额外的 $430$ 美分。（他应该忽略 $40$ 美分的租赁请求。）这样，他每天的总利润为 $725$ 美分。