1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 const int maxn=105;
 5 struct price
 6 {
 7     int val;
 8     int num;
 9 };
10 price sta[maxn];
11 int dp[100010];
12 int main()
13  {
14     int n,m,i,j,ans;
15     while(scanf("%d%d",&n,&m),n+m)
16     {
17         
18         for(i=0;i<n;i++)
19             scanf("%d",&sta[i].val);
20         for(ans=i=0;i<n ;i++)
21         {
22           scanf("%d",&sta[i].num);
23             ans+=sta[i].val*sta[i].num ;
24         }
25         int tem=ans<m?ans:m;
26         if(tem<0)
27         {
28             printf("0\n");
29         continue;
30         }
31         memset(dp,-1,sizeof(dp[0])*(tem+1));
32         dp[0]=0;
33         for(i=0;i<n;i++)
34         {
35             if(sta[i].num*sta[i].val>=tem)  //完全背包
36             {
37                 for(j=sta[i].val ;j<=tem;j++)
38                 {
39                     if(dp[j-sta[i].val]>-1&&dp[j]<dp[j-sta[i].val]+sta[i].num)
40                         dp[j]=dp[j-sta[i].val]+sta[i].num;
41                 }
42             }
43             else
44             {
45                 int k=1;
46                 while(sta[i].num>=k)
47                 {
48                     for(j=tem ;j>=k*sta[i].val ; j--)
49                     {
50                       if(dp[j-k*sta[i].val]>-1&&dp[j]<dp[j-k*sta[i].val]+k)
51                         dp[j]=dp[j-k*sta[i].val]+k;
52                     }
53                     sta[i].num-=k;
54                     k<<=1;
55                 }
56                    
57                  for(j=tem ;j>=sta[i].num ;j--)
58                  {
59                     if(j<sta[i].num*sta[i].val) break;
60                     if(dp[j-sta[i].num*sta[i].val]>-1&&dp[j]<dp[j-sta[i].num*sta[i].val]+sta[i].num)
61                         dp[j]=dp[j-sta[i].num*sta[i].val]+sta[i].num;
62                  }
63 
64             }
65         }
66         ans=0;
67         for(i=1;i<=tem;i++)
68         {
69             if(dp[i]!=-1)ans++;
70         }
71         printf("%d\n",ans);
72     }
73     return 0;
74  }