Master Plan

Because of Eid-ul-Fitr, there is a BIG OFFER at your nearest super shop. You have decided to go shopping with your family at that super shop.

In the super shop, there are $N$ types of products. The rule of the offer is that each person can buy each type of product only once, but they can buy multiple products of different types. Every $i’th$ product have price $P_i$ and weight $W_i$ written on it.

You and your family want to buy as many valuable products as possible, but there is a limitation. Since each person is of a different age, they cannot carry the same amount of weight. Your have $F$ persons in your family including you. You know $i’th$ person can carry maximum $FW_i$ amount of weight.

Now your role is to create a master plan and calculate the maximum value of products that you and your family can buy from the offer.

Input

The first line contains one integer $T$ $(1 \le T \le 10^{3})$ — the number of test cases. Then $T$ test cases follow.

Each test case begins with a single integer $N$ $(1 \le N \le 100)$ — indicates the number of products. Then follows $N$ lines, each containing two integers: $P_i$ $(1 \le P_i \le 100)$ and $W_i$$(1 \le W_i \le 30)$ — indicate the price of the product and the weight of the product respectively. Next line contains a single integer $F$ $(1 ≤ F ≤ 100)$ — the number of persons in your family including you. Next $F$ lines contains maximal weight $FW_i$ $(1 ≤ FW_i ≤ 30)$ that can carry by $i’th$ person from your family.

Output

For every test case output a single integer — the maximal value of products you and your family can buy using the offer.

Sample

Input	Output
1 3 32 20 8 10 93 30 2 27 25	64

Be careful about the newline(‘\n’) at the end.