UVA-10130 :: SuperSale

#include <iostream>
#include <bits/stdc++.h>
using namespace std ;
int price[1005] , weight[1005] ,mx ,n ,dp[1005][35] ;

int func(int i , int w)
{
    if (i>n) return 0 ;
    if (dp[i][w] != -1) return dp[i][w] ;

     int prft1=0 , prft2=0 ;
    if (w+weight[i]<=mx) prft1=price[i]+func(i+1,w+weight[i]) ;
    else prft1=0 ;
    prft2=func(i+1,w) ;

    dp[i][w]=max(prft1,prft2) ;

    return  dp[i][w] ;
}
int main ()
{
    int t ,i ,it ,g ;
    cin>>t ;

    for (it=1 ; it<=t ; it++)
    {
        cin>>n ;
       for (i=1 ; i<=n ; i++)  cin>>price[i]>>weight[i] ;

        cin>>g ;
        int sum=0 ;
        for (i=1 ; i<=g ; i++)
        {
             memset(dp,-1,sizeof(dp)) ;
            cin>>mx ;
            sum=sum+func(1,0) ;
        }
         cout<<sum<<endl ;
    }
    return 0 ;
}