Uva10130

/* Combination using DP
#include <stdio.h>
#include <math.h>
#define SZ 500
int N,R;
int Dp_arr[SZ][SZ];

void init()
{
	for (int i = 0; i < SZ; i++){
		for (int j = 0; j < SZ; j++){
			Dp_arr[i][j] = -1;
		}
	}
}

void take_input()
{
	scanf_s("%d", &N);
	scanf_s("%d", &R);
}

int Combination(int n, int r){
	if (r == 1){
		return n;
	}
	if (n == r){
		return 1;
	}

	if (Dp_arr[n][r] != -1){
		return Dp_arr[n][r];
	}

	Dp_arr[n][r] = Combination(n - 1, r) + Combination(n - 1, r - 1);

	return Dp_arr[n][r];
}

int main()
{

	init();
	take_input();
	int res = Combination(N, R);

	printf("%d\n", res);

	return 0;
}
*/




/*void take_input(){
	scanf("%d", &N);

	for (int i = 0; i < N; i++){
		scanf("%d %d", &Weight_arr[i], &Cost_arr[i]);
	}
	scanf("%d", &W);
}*/




//uva10130

#include <stdio.h>
#include <math.h>


#define SZ 500+510
#define MX(a,b) a>b?a:b

int N, W,Test_cases,cap;
int Weight_arr[SZ], Cost_arr[SZ];
int Dp[SZ][SZ];


void init()
{
	for (int i = 0; i < SZ; i++){
		for (int j = 0; j < 33; j++){
			Dp[i][j] = -1;
		}
	}
}

int napesake(int i, int w, int cap){

	int profit1,profit2;

	if (Dp[i][w] != -1){
		return Dp[i][w];
	}

	if (i >= N){
		return 0;
	}

	if (w + Weight_arr[i] <= cap){
		profit1 = Cost_arr[i] + napesake(i + 1, w + Weight_arr[i],cap);
	}
	else{
		profit1 = 0;
	}

	profit2 = napesake(i + 1, w,cap);

	return Dp[i][w] =  MX(profit1, profit2);
}

int main()
{


	/*freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);*/

	scanf("%d", &Test_cases);

	for (int i = 0; i < Test_cases; i++){
		int res = 0;


		scanf("%d", &N);

		for (int i = 0; i < N; i++){
			scanf("%d %d", &Cost_arr[i],&Weight_arr[i]);
		}
		scanf("%d", &W);

		for (int j = 0; j < W; j++){

			scanf("%d", &cap);
			init();
			res += napesake(0, 0,cap);
		}

		printf("%d\n", res);
	}



	return 0;

}