HDU 2602

#include<stdio.h>

#include<string.h>
#define max(a,b) (a>b?a:b)
__int64 dp[2000000];
int a[1200],b[1200];
int main()
{
   int t,n,i,j,v;
   scanf("%d",&t);
   while(t--)
   {
       memset(dp,0,sizeof(dp));
       scanf("%d%d",&n,&v);      
       for(i=0;i<n;i++)
           scanf("%d",&a[i]);
       for(i=0;i<n;i++)
           scanf("%d",&b[i]);
       for(i=0;i<n;i++)
           for(j=v;j>=b[i];j--)
               dp[j]=max(dp[j],dp[j-b[i]]+a[i]);
           printf("%d\n",dp[v]);
   }
    return 0;
}