#include #include typedef long long llint; using namespace std; const llint INF = 1e18; const int KIJUN = 900000; bool inmin(llint &a, const llint b) { if(b < a) { a = b; return true; } return false; } int main() { int N; llint M; if(scanf("%d%lld", &N, &M) == EOF) { return 0; } int A[N]; for(int i = 0; i < N; i++) { if(scanf("%d", A + i) == EOF) { return 0; } } llint K[N]; for(int i = 0; i < N; i++) { if(scanf("%lld", K + i) == EOF) { return 0; } } llint max = 0; for(int i = 0; i < N; i++) { max += K[i] * (llint)(A[i]); } if(M > max) { printf("-1\n"); return 0; } llint ans = 0; llint tgt = max - M; if(tgt > KIJUN) { llint num = (tgt - KIJUN) / A[N - 1]; ans += num; tgt -= (num * A[N - 1]); } llint dp[tgt + 1]; fill(dp, dp + tgt + 1, INF); dp[0] = 0; for(int i = 0; i < N; i++) { for(int j = 0; j + A[i] <= tgt; j++) { inmin(dp[j + A[i]], dp[j] + 1); } } if(dp[tgt] == INF) { printf("-1\n"); } else { printf("%lld\n", dp[tgt] + ans); } return 0; }