0/1 Knapsack

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <climits>

#include <map>

using namespace std;

#define siz 1000005

#define INF INT_MIN

typedef long long ll;



int dp[siz],query[siz];

map <int,int>mp;

int qMax;

struct data{

    int price,weight;

}a[siz];



void reset(){

    for(int i=0;i<=qMax;i++) dp[i]=INF;

}



bool cmp(data a, data b){

    if(a.weight<b.weight) return true;

    return false;

}

int main()

{

    int n,m,q,price,weight;

    //freopen("input.txt","r",stdin);

    scanf("%d",&n);

    for(int t=0;t<n;t++){

        scanf("%d",&m);

        for(int i=0;i<m;i++){

            scanf("%d%d",&price,&weight);

            a[i].price=price;

            a[i].weight=weight;

        }

        sort(a,a+m,cmp);

        scanf("%d",&q);

        qMax=0;

        for(int i=0;i<q;i++){

            scanf("%d",&query[i]);

            qMax=max(qMax,query[i]);

        }



        reset();

        dp[0]=0;

        for(int i=0;i<m;i++){

            for(int j=qMax;j>=0;j--){

                if(dp[j]!=INF){

                    int val=j+a[i].weight;

                    if(val<=qMax){

                        if(dp[val]==INF) dp[val]=a[i].price+dp[j];

                        else dp[val]=max(dp[val],dp[j]+a[i].price);

                    }

                }

            }

        }

        ll sum=0,mx=0;

        //for(int i=0;i<=qMax;i++) cout<<i<<" "<<dp[i]<<endl;

        int k=0;

        sort(query,query+q);

        int flag=0;

        for(int i=0;i<=qMax;i++){

            mx=max(mx,(ll)dp[i]);

            if(i==query[k]){

                while(true){

                    sum+=mx;

                    if(k==q){

                        flag=1;

                        break;

                    }

                    if(i!=query[k+1]) break;

                    k++;

                }

                k++;

            }

            if(flag==1) break;

            //cout<<"s"<<sum<<endl;

        }

        cout<<sum<<endl;

    }

    return 0;

}