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 \(N\) cows (\(1 \leq N \leq 100,000\)), each capable of producing
some amount of milk every day. The \(M\) stores near FJ's farm
(\(1 \leq M \leq 100,000\)) each offer to buy a certain amount of milk at a
certain price. Moreover, Farmer John's \(R\) (\(1 \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.

Problem credits: Jay Leeds

Problem credits: Jay Leeds

The first line in the input contains \(N\), \(M\), and \(R\). The next \(N\) lines each
contain an integer \(c_i\) (\(1 \leq c_i \leq 1,000,000\)), indicating that Farmer
John's \(i\)th cow can produce \(c_i\) gallons of milk every day. The next \(M\) lines
each contain two integers \(q_i\) and \(p_i\) (\(1 \leq q_i, p_i \leq 1,000,000\)),
indicating that the \(i\)th store is willing to buy up to \(q_i\) gallons of milk
for \(p_i\) cents per gallon. Keep in mind that Farmer John can sell any amount
of milk between zero and \(q_i\) gallons to a given store. The next \(R\) lines each
contain an integer \(r_i\) (\(1 \leq r_i \leq 1,000,000\)), indicating that one of
Farmer John's neighbors wants to rent a cow for \(r_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
output might be too large to fit into a standard 32-bit integer, so you may need
to use a larger integer type like a "long long" in C/C++.

riseoj 작성

출처 올림피아드 > USACO > 2017-2018 > January > Silver