#PU787. USACO 2018 January Contest, Silver — Problem 2. Rental Service

    ID: 1505 传统题 文件IO:rental 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高 上传者: 标签>USACO赛事:jan18来源:usaco.orgscoring:equal_test_cases动态规划

USACO 2018 January Contest, Silver — Problem 2. Rental Service

USACO 2018 January Contest, Silver — Problem 2. Rental Service

题目描述

Farmer John realizes that the income he receives from milk production is insufficient to fund the growth of his farm, so to earn some extra money, he launches a cow-rental service, which he calls "USACOW" (pronounced "Use-a-cow"). Farmer John has NN cows (1≤N≤100,0001 \leq N \leq 100,000), each capable of producing some amount of milk every day. The MM stores near FJ's farm (1≤M≤100,0001 \leq M \leq 100,000) each offer to buy a certain amount of milk at a certain price. Moreover, Farmer John's RR (1≤R≤100,0001 \leq R \leq 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.

输入格式

The first line in the input contains NN, MM, and RR. The next NN lines each contain an integer cic_i (1≤ci≤1,000,0001 \leq c_i \leq 1,000,000), indicating that Farmer John's iith cow can produce cic_i gallons of milk every day. The next MM lines each contain two integers qiq_i and pip_i (1≤qi,pi≤1,000,0001 \leq q_i, p_i \leq 1,000,000), indicating that the iith store is willing to buy up to qiq_i gallons of milk for pip_i cents per gallon. Keep in mind that Farmer John can sell any amount of milk between zero and qiq_i gallons to a given store. The next RR lines each contain an integer rir_i (1≤ri≤1,000,0001 \leq r_i \leq 1,000,000), indicating that one of Farmer John's neighbors wants to rent a cow for rir_i cents per day.

输出格式

The output should consist of one line containing the maximum profit Farmer John can make per day by milking or renting out each of his cows. Note that the

数据范围

(见题面原文)

样例

样例 1

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.
Problem credits: Jay Leeds