#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main () {
	int N; ll K;
	cin >> N >> K;
	std::vector<ll> A(N), B(N);
	for (auto& a : A) {
		cin >> a;
	}
	for (auto& b : B) {
		cin >> b;
	}
	int L = *max_element(A.begin(), A.end());
	vector<ll> C(L + 1, 0ll);
	map<int, int> X;
	for (int i = 0; i < N; i ++) {
		X.clear();
		int a = A[i], b = B[i];
		for (int x = 1; x * x <= a; x ++) {
			if (a % x == 0) {
				int d = b % x;
				d = (d ? x - d : d);
				X[d] = max(X[d], x);
				int y = a / x;
				d = b % y;
				d = (d ? y - d : d);
				X[d] = max(X[d], y);
			}
		}
		int c1 = 1, c2 = 0;
		for (auto& [k, v] : X) {
			if (c1 < v) {
				C[c1+1] += (k - c2);
				c2 = k;
				c1 = v;
			}
		}
		C[a+1] = K;
	}
	for (int i = 0; i <= L; i ++) {
		K -= C[i];
		if (K < 0) {
			cout << i-1 << endl;
			return 0;
		}
	}
	cout << L << endl;
}