Combo Deal

A fast food store offers a series of “combo meal deals” in addition to individually priced items. For example, the menu at the store may look like this: Hamburger Fries Pop Ice Cream Value Meal (1 Hamburger, 1 Fries, 1 Pop) Lovers-Only (2 Hamburgers, 2 Fries, 2 Pops, 1 Ice Cream) Buying a combo is cheaper than buying its items individually. $3.49 $0.99 $1.09 $2.19 $4.79 $9.99 A parent of many kids (or a coach of many students) face this recurring problem: I need to get, say, 9 hamburgers, 6 fries, and 8 pops. How do I fit this into the menu, using the combo deals optimally, so as to pay as little as possible? Note that I am a conservativist, so I don’t buy more food than I need. Input The input contains several test cases, each of them with a menu and several orders. 1. Menu: Individual items, then combos. (a) Individual items: number of items I ≤ 6, then their prices (at most $10 each). (b) Combos: number of combos (at most 8), then for each combo, its composition as an I-tuple of quantities and its price. Example: the sample input below encodes the menu above. 2. Orders: number of orders (at most 10), then for each order, an I-tuple of the wanted quantities. Each element in the tuples is at most 9. All prices are integers in cents. Output For each order of each case, output the minimum payment in cents on its own line. Sample Input 4 349 99 109 219 2 1 1 1 0 479 2 2 2 1 999 2 9680 9685

2/2 Sample Output 4139 4700