SuperSale

题目描述

一个超市里有一个特卖会。每个人只能一种物品买一样，像是一台电视，一根胡萝卜，但价格特别低。我们要和全家人一起去那个超市。 每个人可以从特卖会上拿走他/她能承受重量的物品。我们已经给出了物品的价格和重量的清单。我们也知道，每个人能够承受的最大重量是什么。我们在特卖会上能买到的物品的最大价值是什么？

输入格式

输入由 $T$ 组数据组成。它们的数量（ $1≤T≤1000$ ）在入文件的第一行给出。每组数据的开输头第一行包含一个整数 $N$，表示物品的数量（ $1≤N≤1000$ ）。然后是 $N$ 行，每行包含两个整数。 $P$ 和 $W$ 。 第一个整数（ $1≤P≤100$ ）对应物品的价格。第二个整数（ $1≤W≤30$ ）对应物体的重量。下一行包含一个整数（ $1≤G≤100$ ），它是我们家的人数。接下来的 $G$ 行包含每个人能承受最大的重量（ $1≤MW≤30$ ），接下来的第 $i$ 行对应我们家第 $i$ 个人（ $1≤i≤G$ ）。

输出格式

对于每组数据，打印出我们可以购买的最大商品价值。

样例 #1

样例输入 #1

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

样例输出 #1

72
514