10130 - SuperSale

#include<bits/stdc++.h>
#define sz 1003
using namespace std;

int profit[sz][sz];
int values[sz];
int weight[sz];
int store[102];

int main()
{
    int items,knapsack_weight,i,j,w,a,b,test,G,sum;
    scanf("%d",&test);
    while(test--)
    {
        scanf("%d",&items);
        for(i=0;i<=items;i++)
        {
            profit[i][0]=0;

        }

        for(j=0;j<=1000;j++)
        {
            profit[0][j]=0;
        }

        for(i=1;i<=items;i++)
        {
            scanf("%d%d",&values[i],&weight[i]);
        }

        scanf("%d",&G);

        knapsack_weight = 0;

        for(i=1;i<=G;i++)
        {
            scanf("%d",&store[i]);
            knapsack_weight=max(knapsack_weight,store[i]);
        }

        for(i=1;i<=items;i++)
        {
            for(w=1;w<=knapsack_weight;w++)
            {
                if(weight[i]>w)
                {
                    profit[i][w]=profit[i-1][w];
                }
                else
                {
                    a = profit[i-1][w];
                    b = profit[i-1][w-weight[i]]+values[i];
                    if(a>b)
                    {
                        profit[i][w]=a;
                    }
                    else
                    {
                        profit[i][w]=b;
                    }
                }
            }
        }
        sum=0;
        for(i=1;i<=G;i++)
        {
            sum+=profit[items][store[i]];
        }
        printf("%d\n",sum);
    }
    return 0;
}