Cacher is the code snippet organizer for pro developers

import java.util.Scanner;
public class Main
{
	static int[][] c;
	static int[] cost,weight;
    public static void main(String[] args)
    {
    	Scanner sc=new Scanner(System.in);
    	int test=sc.nextInt();
    	while(test-->0)
    	{
    		int N=sc.nextInt(),ans=0;
    		c=new int[1001][31];
    		cost=new int[N+1];
    		weight=new int[N+1];
    		for(int i=1;i<N+1;++i)
    		{
    			cost[i]=sc.nextInt();
    			weight[i]=sc.nextInt();
    		}
    		int G=sc.nextInt();
    		int[] pack=new int[G+1];
    		for(int i=1;i<G+1;++i)
    			pack[i]=sc.nextInt();
    		for(int i=1;i<G+1;++i)
    			ans+=knapsack(N,pack[i]);
    		System.out.println(ans);
    	}
    }

	public static int knapsack(int n, int w) 
	{
		if (w<0) 
			return -100000; 
	    if (n==0) 
	    	return 0;
	    if (c[n][w]!=0) 
	    	return c[n][w];
	    return c[n][w]=Math.max(knapsack(n-1, w-weight[n])+cost[n], knapsack(n-1, w));
	}
}

#include<stdio.h>
#include<stdlib.h>
int cost[1000], weight[1000];
int c[10000];
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		 memset(c, 0, sizeof(c));
		int i,n;
		scanf("%d",&n);
		for(i=0;i<n;i++){
			scanf("%d %d",&cost[i],&weight[i]);
		}
		int g,w,tot=0;
		scanf("%d",&g);
		for(i=0;i<g;i++){
			scanf("%d",&w);
			tot+=knapsack(n, w);
		}
		printf("%d\n",tot);
	}
	
	system("PAUSE");
	return 0;
}
int knapsack(int n, int w)
{
  
   int k=0;
   for(;k<10000;k++)
   	c[k]=0;
 	int i,j;
    for (i = 0; i < n; ++i)
        for (j = w; j - weight[i] >= 0; --j) {
		   // 由後往前
            if(c[j]< c[j - weight[i]] + cost[i])
            	c[j]= c[j - weight[i]] + cost[i];
}
    return c[w];
}