#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define INF 1e9 int n;//n種硬幣 int m;//購買商品的價值 int up_bound;//DP價值上界 int val[100+5];//每種硬幣價值 int num[100+5];//每種硬幣數目 int dp[55555]; //多重背包 int dp2[55555];//完全背包 //1次01背包 void ZERO_ONE_PACK(int *dp,int cost,int sum) { for(int i=up_bound;i>=cost;i--) dp[i] = min(dp[i], dp[i-cost]+sum);//注意這里是+sum } //1次完全背包 void COMPLETE_PACK(int *dp,int cost) { for(int i=cost;i<=up_bound;i++) dp[i] = min(dp[i], dp[i-cost]+1); } //1次多重背包 void MULTIPLY_PACK(int *dp,int cost,int sum) { if(cost*sum>=up_bound) { COMPLETE_PACK(dp,cost); return ; } int k=1; while(k<sum) { ZERO_ONE_PACK(dp,cost*k,k); sum -=k; k *=2; } ZERO_ONE_PACK(dp,cost*sum,sum); } int main() { while(scanf("%d%d",&n,&m)==2) { //讀取輸入+計算上界 int max_val=0; for(int i=1;i<=n;i++) { scanf("%d",&val[i]); max_val= max(max_val,val[i]); } for(int i=1;i<=n;i++) scanf("%d",&num[i]); up_bound=max_val*max_val+m;//上界 //初始化dp和dp2 for(int i=1;i<=up_bound;i++) dp[i]=dp2[i]=INF; dp[0]=dp2[0]=0; //遞推進程 for(int i=1;i<=n;i++) { MULTIPLY_PACK(dp,val[i],num[i]); COMPLETE_PACK(dp2,val[i]); } //統計結果 int ans=INF; for(int i=m;i<=up_bound;i++) ans= min(ans, dp[i]+dp2[i-m]); printf("%d ",ans==INF?⑴:ans); } return 0; }