No submission language available for this problem.

疯狂折扣

题目背景

轰轰一家子听说，超市进行大打折，听说能"打成骨折"哦。那天晚上他们全家人都去了……。

题目描述

每人均可以购买每种商品，但这个商品只允许购买 $1$ 个。

每人在他能够拎得动的重量之内，可以拿很多商品(即不超过他最大能拿的商品总重量)。

现在给出商品的价格与重量的信息表，并给出每个人能拿的商品总重量，求这一家人购买商品的最大总价值。

输入格式

数据具有多组数据。

第一行一个整数 $T$，共有 $T$ 个数据。

接下来 $T$ 组数据，

第一行一个正整数 $N$，表示疯狂折扣的商品个数。

随后 $N$ 行给出两个整数 $p_i，w_i$，代表第 $i$ 个商品的价格与重量。

随后一行一个整数 $g$，代表这一家子总人数。

再 $g$ 行给出一个整数 $g_i$，代表第 $i$ 个人能拿的最大商品总重量。

输出格式

对于每组数据，输出一行一个整数，代表这一家人购买商品的最大总价值。

样例 #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

提示

样例一说明

共 $2$ 组数据求。

第 $1$ 组，$3$ 个商品，价格(单位: $p$)与重量(单位: $w$)是:

72p 17w
44p 23w
31p 24w

这一家人只有 $1$ 人去了，他最重能拿 $26w$，只能选择第一个商品是最大价值 $72$。

数据规模与约定

题目数据组：$1\leq T\leq 1000$, 疯狂折扣商品数：$0\leq N\leq 1000$, 每件商品价格：$1\leq p_i\leq 100$, 每件商品重量：$1\leq w_i\leq 30$, 这家人数量：$1\leq g\leq 100$, 每个人最大能拿的商品总重量：$1\leq g_i\leq 30$