# 2018 USACO January

# 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 **n** cows, each capable of producing some amount of milk every day. The **m** stores near FJ's farm each offer to buy a certain amount of milk at a certain price. Moreover, Farmer John's **r** 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.

#### Input

The first line contains **n** (**1** ≤ **n** ≤ `10`

), ^{5}**m** (**1** ≤ **m** ≤ `10`

) and ^{5}**r** (**1** ≤ **r** ≤ `10`

). The next ^{5}**n** lines each contain an integer `c`

(_{i}**1** ≤ `c`

≤ _{i}`10`

), indicating that Farmer John's ^{6}**i**-th cow can produce `c`

gallons of milk every day. The next _{i}**m** lines each contain two integers `q`

and _{i}`p`

(_{i}**1** ≤ `q`

, _{i}`p`

≤ _{i}`10`

), indicating that the ^{6}**i**-th store is willing to buy up to `q`

gallons of milk for _{i}`p`

cents per gallon. Keep in mind that Farmer John can sell any amount of milk between zero and _{i}`q`

gallons to a given store. The next _{i}**r** lines each contain an integer `r`

(_{i}**1** ≤ `r`

≤ _{i}`10`

), indicating that one of Farmer John's neighbors wants to rent a cow for ^{6}`r`

cents per day._{i}

#### Output

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++.

#### Example

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.

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

725