SuperSale UVa 10130 Solution

    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <stack>
    using namespace std;
    int kn(vector<vector<int> > &dp,vector<int> &p,vector<int> &w,int n,int i,int fw){
        if(i==n+1)return 0;
        if(dp[i][fw]!=-1)return dp[i][fw];
        if(w[i]>fw)return dp[i][fw]=kn(dp,p,w,n,i+1,fw);
        return dp[i][fw]=max(kn(dp,p,w,n,i+1,fw),p[i]+kn(dp,p,w,n,i+1,fw-w[i]));
    }
    int main(){
        int t;
        cin>>t;
        while(t--){
            int n;
            cin>>n;
            vector<int> p(n+1),w(n+1);
            int i=0;
            while(i++<n)cin>>p[i]>>w[i];
            int g;
            cin>>g;
            vector<int> f(g+1);
            i=0;
            while(i++<g)cin>>f[i];
            i=1;
            int sum=0;
            while(i<=g){
                vector<vector<int> > dp(n+1,vector<int>(f[i]+1,-1));
                sum+=kn(dp,p,w,n,1,f[i]);
                i++;
            }
            cout<<sum<<endl;
        }
    }