#include <stdio.h>
#include <algorithm>
#include <string.h>
#define MAX_N 1000
#define MAX_W 1000
using namespace std;
int n;
int dp[1002][40];
int weight[MAX_W+1];
int cost[MAX_N+1];
int knapsack(int i,int w, int cap)
{
if(i==n+1) return 0;
if(dp[i][w]!=-1) return dp[i][w];
int profit1=0,profit2=0;
if(w+weight[i]<=cap)
profit1=cost[i]+knapsack(i+1,w+weight[i],cap);
profit2=knapsack(i+1,w,cap);
dp[i][w]=max(profit1,profit2);
return dp[i][w];
}
int main()
{
int T ;
int result[MAX_N];
scanf("%d",&T);
for(int j=0;j<T;j++)
{
int N;
scanf("%d", &N);
n = N;
memset(weight,-1,sizeof(weight));
memset(cost,-1,sizeof(cost));
for(int nob=0; nob<N; nob++)
{
scanf("%d %d", &cost[nob], &weight[nob]);
}
int G, ans = 0;
scanf("%d", &G);
int CAP;
while(G--)
{
scanf("%d", &CAP);
memset(dp,-1,sizeof(dp));
ans = ans + knapsack(0,0,CAP);
}
result[j] = ans;
}
for(int i=0;i<T;i++)
{
printf("%d\n", result[i]);
}
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxhbGdvcml0aG0+CiNpbmNsdWRlIDxzdHJpbmcuaD4KI2RlZmluZSBNQVhfTiAxMDAwCiNkZWZpbmUgTUFYX1cgMTAwMAoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBuOwppbnQgZHBbMTAwMl1bNDBdOwppbnQgd2VpZ2h0W01BWF9XKzFdOwppbnQgY29zdFtNQVhfTisxXTsKCmludCBrbmFwc2FjayhpbnQgaSxpbnQgdywgaW50IGNhcCkKewoJaWYoaT09bisxKSByZXR1cm4gMDsgCglpZihkcFtpXVt3XSE9LTEpIHJldHVybiBkcFtpXVt3XTsgCgkJaW50IHByb2ZpdDE9MCxwcm9maXQyPTA7CgkJaWYodyt3ZWlnaHRbaV08PWNhcCkgCgkJCXByb2ZpdDE9Y29zdFtpXStrbmFwc2FjayhpKzEsdyt3ZWlnaHRbaV0sY2FwKTsKCXByb2ZpdDI9a25hcHNhY2soaSsxLHcsY2FwKTsgCglkcFtpXVt3XT1tYXgocHJvZml0MSxwcm9maXQyKTsgCglyZXR1cm4gZHBbaV1bd107Cn0KCmludCBtYWluKCkKewoJaW50IFQgOwoJaW50IHJlc3VsdFtNQVhfTl07CglzY2FuZigiJWQiLCZUKTsKCWZvcihpbnQgaj0wO2o8VDtqKyspCgl7CgkJaW50IE47CgkJc2NhbmYoIiVkIiwgJk4pOwoJCW4gPSBOOwoJCW1lbXNldCh3ZWlnaHQsLTEsc2l6ZW9mKHdlaWdodCkpOwoJCW1lbXNldChjb3N0LC0xLHNpemVvZihjb3N0KSk7CgkJZm9yKGludCBub2I9MDsgbm9iPE47IG5vYisrKQoJCXsKCQkJc2NhbmYoIiVkICVkIiwgJmNvc3Rbbm9iXSwgJndlaWdodFtub2JdKTsKCQl9CgkJaW50IEcsIGFucyA9IDA7CgkJc2NhbmYoIiVkIiwgJkcpOwoJCWludCBDQVA7CgkJd2hpbGUoRy0tKQoJCXsKCQkJc2NhbmYoIiVkIiwgJkNBUCk7CgkJCW1lbXNldChkcCwtMSxzaXplb2YoZHApKTsKCQkJYW5zID0gYW5zICsga25hcHNhY2soMCwwLENBUCk7CgkJfQoJCXJlc3VsdFtqXSA9IGFuczsKCgl9CgoJZm9yKGludCBpPTA7aTxUO2krKykKCXsKCQlwcmludGYoIiVkXG4iLCByZXN1bHRbaV0pOwoJfQoKfQ==