1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #define INF 0x3f3f3f3f 8 using namespace std; 9 const int maxn=1e4+10;10 int dp[maxn];11 int weight[505];12 int money[505];13 int main()14 {15 int T;16 scanf("%d",&T);17 while(T--)18 {19 // memset(dp,0,sizeof(dp));20 int E,F;21 scanf("%d%d",&E,&F);22 int v=F-E;23 for(int i=0;i<=v;i++)24 {25 dp[i]=INF;26 }27 dp[0]=0;28 int n;29 scanf("%d",&n);30 for(int i=1;i<=n;i++)31 {32 scanf("%d%d",&money[i],&weight[i]);33 }34 for(int i=1;i<=n;i++)35 {36 for(int k=weight[i];k<=v;k++)37 {38 dp[k]=min(dp[k],dp[k-weight[i]]+money[i]);39 }40 }41 if(dp[v]