Shopping Spree

Acme Super Store is having a contest to give away shopping sprees to lucky families. If a family wins a shopping spree each person in the family can take any items in the store that he or she can carry out, however, each person can only take one of each type of item. For example, one family member can take one television, one watch, and one toaster, while another family member can take one television, one camera and one pair of shoes. Each item has a price(in dollars)and a weight(in pounds)and each person in the family has a limit in the total weight they can carry. Two people can not work together to carry a single object. Your job is to help the families select items for each person to carry to maximize the total price of all items the family takes. What is the maximum price of items the family can select?

Input: The input file named shopping.txt consists of T test cases

?T(1 ? T ? 100)is given on the first line of the input file.

?Each test case begins with a line containing a single integer number N that indicates the number of items(1 ? N ? 100) in that test case

?Followed by N lines, each containing two integers:P and W. The first integer (1 ? P ? 1000) corresponds to the price of object and the second integer (1 ? W ? 100) corresponds to the weight of object.

?The next line contains one integer (1 ? F? 100) which is the number of people in that family.

?The next F lines contains the maximum weight (1 ? M? 100) that can be carried by their person in the family (1 ? i ? F).

Output: Written to a file namedshopping.out. For each test case your program should calculate one integer which is the maximum total price of all goods that the family in can carry out during their shopping spree.

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