10898 - Combo Deal

速食店除了提供食物的單點之外,通常也會提供「套餐」的選擇。例如:菜單可能像這樣:

品名 價格
Hamburger (漢堡) \$3.49
Fries (薯條) \$0.99
Pop (爆米花) \$1.09
Ice Cream (冰淇淋) \$2.19
Value Meal (1 Hamburger, 1 Fries, 1 Pop) (超值套餐) \$4.79
Lovers-Only (2 Hamburgers, 2 Fries, 2 Pops, 1 Ice Cream) (情侶套餐) \$9.99

買套餐組合會比各項單獨買來的便宜。(廢話,否則誰會買套餐。)

一個有很多小孩的媽媽面臨了一種情況:比方說,我需要 9 份漢堡,6 份薯條和 8 份爆米花,我要如何從菜單選擇可以買到我所需要的,而且付的錢最少?請注意:我是一個保守主義者,所以我絕不會買比需要多的食物

Input

輸入含有多筆測資,每筆測資含有菜單及幾個訂單。

  1. 菜單:先個別單點,然後是組合套餐。
    1. 個別單點:有一個整數 $I$ ($I\leq{6}$),然後是各單點的價格 (每項最多 \$10)
    2. 組合套餐:有一個整數代表有多少種組合套餐 (最多 8 種)。接下來就是每種組合套餐的內容:包含各項單點的 $I$ 個數目,然後是價錢。
      以下的 Sample Input 的菜單即是上面所敘述的。
  2. 訂單:訂單的數目 (最多 10),然後是各訂單的內容 ($I$ 個數字代表所需各項目的數量,每個數字最多為 9)

所有的價格均以分 (cent) 為單位。(1 dollar = 100 cent)

Output

對於每筆測資的每個訂單,輸出一列,最少要付多少錢才能買到他所需要的食物。

Sample Input

4 349 99 109 219
2
1 1 1 0 479
2 2 2 1 999
2
9 6 8 0
9 6 8 5

Sample Output

4139
4700