#include<iostream>
#include<string>
using namespace std;
int weights[1005],num_person;
int prices[1005],person_max;int takeItem, skipItem;;
int waight,price,num,sum=0,arr[1005][35];
int solve(int index, int weight)
{
if(arr[index][weight]!=-1)
return arr[index][weight];
if(index==num)
{
if(weight <= person_max)
{
return arr[index][weight]=price;
}
else
return arr[index][weight]= 0;
}
int takeItem, skipItem;
if(weight+weights[index]<=person_max)
{
takeItem = solve(index + 1, weight + weights[index])+ price + prices[index];
}
skipItem = solve(index + 1, weight);
return arr[index][weight]=max(takeItem, skipItem);
}
int main()
{
int testCases;
cin>>testCases;
for(int i=0;i<testCases;i++)
{
cin>>num;
for(int j=0;j<num;j++)
{
cin>>prices[j]>>weights[j];
}
cin>>num_person;
for(int j=0;j<num_person;j++)
{
cin>>person_max;
for(int k=0;k<1005;k++)
for(int l=0;l<35;l++)
arr[k][l]=-1;
sum+= solve(0, 0);
}
cout<<sum << endl;
sum=0;
}
return 0;
}
I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPHN0cmluZz4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKaW50IHdlaWdodHNbMTAwNV0sbnVtX3BlcnNvbjsKaW50IHByaWNlc1sxMDA1XSxwZXJzb25fbWF4O2ludCB0YWtlSXRlbSwgc2tpcEl0ZW07OwppbnQgd2FpZ2h0LHByaWNlLG51bSxzdW09MCxhcnJbMTAwNV1bMzVdOwppbnQgc29sdmUoaW50IGluZGV4LCBpbnQgd2VpZ2h0KQp7CgppZihhcnJbaW5kZXhdW3dlaWdodF0hPS0xKQpyZXR1cm4gYXJyW2luZGV4XVt3ZWlnaHRdOwppZihpbmRleD09bnVtKQp7CmlmKHdlaWdodCA8PSBwZXJzb25fbWF4KQp7CnJldHVybiBhcnJbaW5kZXhdW3dlaWdodF09cHJpY2U7Cgp9CmVsc2UKcmV0dXJuIGFycltpbmRleF1bd2VpZ2h0XT0gMDsKfQppbnQgdGFrZUl0ZW0sIHNraXBJdGVtOwppZih3ZWlnaHQrd2VpZ2h0c1tpbmRleF08PXBlcnNvbl9tYXgpCnsKdGFrZUl0ZW0gPSBzb2x2ZShpbmRleCArIDEsIHdlaWdodCArIHdlaWdodHNbaW5kZXhdKSsgcHJpY2UgKyBwcmljZXNbaW5kZXhdOwp9CnNraXBJdGVtID0gc29sdmUoaW5kZXggKyAxLCB3ZWlnaHQpOwpyZXR1cm4gYXJyW2luZGV4XVt3ZWlnaHRdPW1heCh0YWtlSXRlbSwgc2tpcEl0ZW0pOwp9CmludCBtYWluKCkKewppbnQgdGVzdENhc2VzOwpjaW4+PnRlc3RDYXNlczsKZm9yKGludCBpPTA7aTx0ZXN0Q2FzZXM7aSsrKQp7CmNpbj4+bnVtOwpmb3IoaW50IGo9MDtqPG51bTtqKyspCnsKY2luPj5wcmljZXNbal0+PndlaWdodHNbal07Cn0KY2luPj5udW1fcGVyc29uOwpmb3IoaW50IGo9MDtqPG51bV9wZXJzb247aisrKQp7CmNpbj4+cGVyc29uX21heDsKZm9yKGludCBrPTA7azwxMDA1O2srKykKZm9yKGludCBsPTA7bDwzNTtsKyspCmFycltrXVtsXT0tMTsKc3VtKz0gc29sdmUoMCwgMCk7Cn0KY291dDw8c3VtIDw8IGVuZGw7CnN1bT0wOwp9CnJldHVybiAwOwp9