10130 - SuperSale

在SuperHiperMarket賣場有促銷活動，每種商品每人都能用超低的價格各買一件，例如一台超低價電視、一根超低價蘿蔔，我們全家總動員要去大採購，不過每人能提的重量有限。我們已經準備好了欲採購物品的清單，記錄著每件物品的價格與重量，我們也知道自已最多能提多少重量，請問我們這次採購能買到物品的最高總值為何？

Input Specification

1. 第一列為整數T，表示有多少組測試資料。

2. 每組測試資料分為兩部份，第一部份一開始有一整數N，表示接下來共有N件物品，而接下來的每一列為這N件物品的價格(P, 1<=P<=100)與重量(W, 1<=W<=30)。

3. 緊接著第二部份為一整數G，表示群組內的人數，接下來有G列表示每個人最大能提的總重量(MW, 1<=MW<=30)。

Output Specification

請依每組測試資料輸出一個整數：全家人能買到物品的最高總值。

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

Output for the Sample Input

72

514

---

原文出處