1 #include  <map>

 2 #include  <set>

 3 #include  <cmath>

 4 #include  <queue>

 5 #include  <cstdio>

 6 #include  <vector>

 7 #include  <climits>

 8 #include  <cstring>

 9 #include  <cstdlib>

10 #include  <iostream>

11 #include  <algorithm>

12 using namespace std;

13 const int maxm=10000+120*120+5;

14 int dp_pay[maxm],dp_change[maxm];

15 int N,T,v[105],c[105];

16

17 void multi_knapsack(int n,int W){//多重背包，二进制拆分

18     memset(dp_pay,0x3f,sizeof(dp_pay));

19     dp_pay[0]=0;

20     for(int i=1;i<=N;i++){//转化为完全背包

21         if(c[i]*v[i]>=W){

22             for(int j=v[i];j<=W;j++)

23                 dp_pay[j]=min(dp_pay[j],dp_pay[j-v[i]]+1);

24         }

25         else{

26             for(int k=1;c[i]>0;k<<=1){//二进制拆分

27                 int x=min(k,c[i]);

28                 for(int j=W;j>=v[i]*x;j--)

29                     dp_pay[j]=min(dp_pay[j],dp_pay[j-v[i]*x]+x);

30                 c[i]-=x;

31             }

32         }

33     }

34 }

35

36 void complete_knapsack(int n,int W){

37     memset(dp_change,0x3f,sizeof(dp_change));

38     dp_change[0]=0;

39     for(int i=1;i<=N;i++){

40         for(int j=v[i];j<=W;j++)

41             dp_change[j]=min(dp_change[j],dp_change[j-v[i]]+1);

42     }

43 }

44

45 int main(){

46     while(~scanf("%d%d",&N,&T)){

47         int maxv=0,W;

48         for(int i=1;i<=N;i++)

49             scanf("%d",&v[i]),maxv=max(maxv,v[i]);

50         for(int i=1;i<=N;i++)

51             scanf("%d",&c[i]);

52         maxv=maxv*maxv;

53         multi_knapsack(N,maxv+T);

54         complete_knapsack(N,maxv);

55         int ans=0x3f3f3f3f;

56         for(int i=0;i<=maxv;i++)

57             ans=min(ans,dp_pay[i+T]+dp_change[i]);

58         if(ans==0x3f3f3f3f)

59             ans=-1;

60         printf("%d\n",ans);

61     }

62 }