#include <algorithm>
#include <iostream>
#include <map>
#include <ranges>
#include <utility>
#include <vector>
int main() {
    using namespace std;
    using lint = long long;
    int n;
    lint k;
    cin >> n >> k;
    vector<int> a(n), b(n);
    for (auto &e : a) cin >> e;
    for (auto &e : b) cin >> e;

    const int nn = 110000;
    vector isp(nn, 1);
    vector lsp(nn, -1);
    isp[0] = isp[1] = 0;
    lsp[1] = 1;
    for (int p : views::iota(2, nn)) {
        if (!isp[p]) continue;
        lsp[p] = p;
        for (int q = p * 2; q < nn; q += p) {
            isp[q] = 0;
            if (lsp[q] == -1) lsp[q] = p;
        }
    }
    auto divs = [&](int x) {
        vector<int> ans{1};
        while (x > 1) {
            int p = lsp[x];
            int e = 0;
            while (x % p == 0) {
                x /= p;
                e++;
            }
            for (int i = 0, s = ans.size(); i < s; ++i) {
                int d = ans[i] * p;
                for (int ei = 1; ei <= e; ++ei) {
                    ans.push_back(d);
                    d *= p;
                }
            }
        }
        ranges::sort(ans);
        return ans;
    };
    vector<vector<pair<int, int>>> cost(n);
    for (int i : views::iota(0, n)) {
        auto ds = divs(a[i]);
        map<int, int> dcd;
        for (int d : ds) dcd[(b[i] + d - 1) / d * d - b[i]] = d;
        for (auto [c, d] : dcd) {
            if (!cost[i].empty() && cost[i].back().first > d) {
            } else
                cost[i].emplace_back(d, c);
        }
    }
    auto check = [&](int g) {
        lint ans = 0;
        for (auto &ci : cost) {
            auto it = ranges::lower_bound(ci, g, {}, &pair<int, int>::first);
            if (it == ci.end()) return false;
            ans += it->second;
        }
        return ans <= k;
    };
    int ok = 0, ng = ranges::min(a) + 1;
    while (abs(ok - ng) > 1) {
        int mi = (ok + ng) / 2;
        (check(mi) ? ok : ng) = mi;
    }
    cout << ok << "\n";
}