Problem C
Adventurous Creamery Maniacs

Many people enjoy ice cream, especially on a hot day. But some people have a passion for the frozen treat that is unrivaled by any other food-lovers. These people are the members of the Adventurous Creamery Maniacs (ACM), and you have been hired to help cater their weekly meeting. Now, the members of the ACM are quite picky about what flavors of ice cream they want, so they always take ice cream orders in advance. Each member of the club has filled out an order card denoting how much ice cream they want out of three flavors: Chocolate, Vanilla, and Strawberry.

As you are tabulating the survey of the ACM members, you begin to realize the sheer quantity of ice cream you are going to need to buy. Even though the survey was limited to basic flavors that do not have a premium cost, you still are obliged to buy the highest quality ice cream and are concerned about overspending. Because the ACM loves ice cream, they would hate to see any of it go to waste. Therefore, one of the requirements they make of all of their caterers is that they buy the exact quantities of ice cream indicated by their survey (you cannot buy extra, even if it is cheaper).

The ACM has helped you acquire some special discounts with various ice cream suppliers (the ACM is one of their best customers, after all), but this means that there is a possibility that just ordering the largest containers of ice cream may not be the most economical for some flavors of ice cream. Additionally, the ice cream suppliers offer mixed packages of ice cream containing equal amounts of all three of the flavors that you want to buy. These mixed packages are usually sold in different quantities and prices than their single-flavored counterparts, and you realize that buying these multi-flavored packages may be the only way for you to get the lowest price of the exact quantity that you need. Can you figure out the best way to satisfy the ACM’s order?

Input

The first line of input contains three integers: $n~ m~ p$, the target amount of chocolate, vanilla, and strawberry ice cream you need to buy ($1 \leq n, m, p \leq 10^3$). The next line of input includes four integers: $V~ C~ S~ A$, the number of options you have for purchasing Vanilla, Chocolate, Strawberry, and all flavors of ice cream. This will be followed by $V$ ($1 \leq V \leq 10^3$), $C$ ($1 \leq C \leq 10^3$), $S$ ($1 \leq S \leq 10^3$), and $A$ ($0 \leq A \leq 10^3$) lines each of two integers $q c$ ($1 \leq q, c \leq 10^3$), corresponding to the quantity of that flavor of ice cream and the cost to buy that quantity of ice cream. For the line corresponding to all flavors of ice cream, the quantity given corresponds to the amount of each flavor in the pack (so a quantity of $3$ corresponds to $3$ quarts of vanilla, 3 quarts of Chocolate, and 3 quarts of Strawberry in one package).

Note that for a given flavor of ice cream, p and q may not necessarily be unique. You are dealing with multiple ice cream suppliers and they all have different pricing policies.

Output

Output a single line containing the minimum possible cost to buy the ice cream you want. It is safe to assume that every supplier sells $1$-quart containers of each individual flavor of ice cream, so a solution will always be possible.

3 4 5
1 1 1 0
1 1
1 1
1 1

12

4 7 9
2 2 2 1
1 3
3 5
1 3
2 4
1 8
2 10
1 4

51