在 SuperHiperMarket 有一個超級拍賣。每一個人每樣商品只能拿一個,也就是一台電視機,一根紅蘿蔔,一台腳踏車,但是一個人不能拿 2 台電視機。現在有一家人到超級拍賣會去。每個人可以盡可能的拿商品,只要他搬的動。我們手上有所有商品的價格及重量,我們也知道這家人每個人最多能搬的重量。請問這家人能從超級拍賣會搬到的最大價格是多少?
Input
輸入的第一列有一個整數代表以下有多少組測試資料。
每組測試資料的第一列有一個整數 N (1≤N≤1000) 代表有多少種商品。接下來的 N 列每列有 2 個整數 P 和 W,分別代表該項商品的價格和重量 (1≤P≤1000,1≤W≤30)。再下一列有一個整數 G 代表這家共有多少人,再接下來的 G 列每列有一個整數 MW (1≤MW≤30) 代表某個人最多能搬的重量。請參考 Sample Input。
Output
每組測試資料輸出這個家庭能搬到的最大價格是多少。
Sample Input
2
3
72 17
44 23
31 24
1
26
6
64 26
85 22
52 4
99 18
39 13
54 9
4
23
20
20
26
Sample Output
72
514