Cardbluff is popular sport game in Telegram. Each Cardbluff player has ever dreamed about entrance in the professional layer. There are n judges now in the layer and you are trying to pass the entrance exam. You have a number k — your skill in Cardbluff.

Each judge has a number a_i — an indicator of uncertainty about your entrance to the professional layer and a number e_i — an experience playing Cardbluff. To pass the exam you need to convince all judges by playing with them. You can play only one game with each judge. As a result of a particular game, you can divide the uncertainty of i-th judge by any natural divisor of a_i which is at most k. If GCD of all indicators is equal to 1, you will enter to the professional layer and become a judge.

Also, you want to minimize the total amount of spent time. So, if you play with x judges with total experience y you will spend x ⋅ y seconds.

Print minimal time to enter to the professional layer or -1 if it's impossible.

Input

There are two numbers in the first line n and k (1 ≤ n ≤ 10^6, 1 ≤ k ≤ 10^{12}) — the number of judges and your skill in Cardbluff.

The second line contains n integers, where i-th number a_i (1 ≤ a_i ≤ 10^{12}) — the uncertainty of i-th judge

The third line contains n integers in the same format (1 ≤ e_i ≤ 10^9), e_i — the experience of i-th judge.

Output

Print the single integer — minimal number of seconds to pass exam, or -1 if it's impossible

Examples

Input


3 6
30 30 30
100 4 5


Output


18


Input


1 1000000
1
100


Output


0


Input


3 5
7 7 7
1 1 1


Output


-1
#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:512000000")
using namespace std;
using li = long long;
using ld = long double;
void solve(bool);
void precalc();
clock_t start;
int main() {
  start = clock();
  int t = 1;
  cout.sync_with_stdio(0);
  cin.tie(0);
  cout.precision(20);
  cout << fixed;
  precalc();
  while (t--) {
    solve(true);
  }
  cout.flush();
  return 0;
}
template <typename T>
T binpow(T q, T w, T mod) {
  if (!w) return 1 % mod;
  if (w & 1) return q * 1LL * binpow(q, w - 1, mod) % mod;
  return binpow(q * 1LL * q % mod, w / 2, mod);
}
template <typename T>
T gcd(T q, T w) {
  while (w) {
    q %= w;
    swap(q, w);
  }
  return q;
}
template <typename T>
T lcm(T q, T w) {
  return q / gcd(q, w) * w;
}
template <typename T>
void make_unique(vector<T>& vec) {
  sort(vec.begin(), vec.end());
  vec.erase(unique(vec.begin(), vec.end()), vec.end());
}
template <typename T>
void relax_min(T& cur, T val) {
  cur = min(cur, val);
}
template <typename T>
void relax_max(T& cur, T val) {
  cur = max(cur, val);
}
mt19937 rng(
    (unsigned long long)chrono::steady_clock::now().time_since_epoch().count());
void precalc() {}
li dp[2][12][1 << 12];
void solve(__attribute__((unused)) bool read) {
  int n;
  li k;
  if (read) {
    cin >> n >> k;
  } else {
    n = 1e6;
    k = (li)1e12;
  }
  vector<li> a(n), cost(n);
  li g = 0;
  for (int i = 0; i < n; ++i) {
    if (read) {
      cin >> a[i];
    } else {
      a[i] = 200560490130LL;
    }
    g = gcd(a[i], g);
  }
  for (int i = 0; i < n; ++i) {
    if (read) {
      cin >> cost[i];
    } else {
      cost[i] = rand();
    }
  }
  vector<li> primes;
  for (li p = 2; p * p <= g; ++p) {
    if (g % p == 0) {
      primes.push_back(p);
      while (g % p == 0) {
        g /= p;
      }
    }
  }
  if (g > 1) {
    primes.push_back(g);
  }
  if (primes.empty()) {
    cout << "0\n";
    return;
  }
  vector<pair<li, li>> mapa;
  for (int i = 0; i < n; ++i) {
    li cur_val = 1;
    for (int j = 0; j < primes.size(); ++j) {
      auto p = primes[j];
      while (a[i] % p == 0) {
        a[i] /= p;
        cur_val *= p;
      }
    }
    mapa.push_back({cur_val, cost[i]});
  }
  sort(mapa.begin(), mapa.end());
  vector<vector<li>> vecs;
  vector<li> costs;
  for (int i = 0; i < mapa.size();) {
    int j = i;
    vector<li> vec;
    auto cur_val = mapa[i].first;
    vector<li> key(primes.size(), 1);
    for (int r = 0; r < primes.size(); ++r) {
      while (cur_val % primes[r] == 0) {
        cur_val /= primes[r];
        key[r] *= primes[r];
      }
    }
    while (j < mapa.size() && mapa[j].first == mapa[i].first) {
      vec.push_back(mapa[j].second);
      ++j;
    }
    i = j;
    int enough_space = (int)primes.size();
    if (vec.size() > enough_space) {
      vec.resize(enough_space);
    }
    for (li c : vec) {
      vecs.push_back(key);
      costs.push_back(c);
    }
  }
  const li INF = (li)1e18;
  int full_mask = (1 << primes.size()) - 1;
  auto clear_dp = [&](int par) {
    for (int cnt = 0; cnt <= primes.size(); ++cnt) {
      for (int mask = 0; mask <= full_mask; ++mask) {
        dp[par][cnt][mask] = INF;
      }
    }
  };
  int par = 0;
  for (int i = 0; i < 2; ++i) {
    clear_dp(i);
  }
  dp[par][0][full_mask] = 0;
  vector<li> prods;
  for (int i = 0; i < vecs.size(); ++i) {
    for (int cnt = 0; cnt <= primes.size(); ++cnt) {
      for (int mask = 0; mask <= full_mask; ++mask) {
        dp[par ^ 1][cnt][mask] = dp[par][cnt][mask];
      }
    }
    prods.assign(1 << primes.size(), 1);
    for (int mask = 0; mask < (1 << primes.size()); ++mask) {
      for (int j = 0; j < primes.size(); ++j) {
        if (mask & (1 << j)) {
          prods[mask] *= vecs[i][j];
        }
      }
    }
    for (int cnt = 0; cnt <= primes.size(); ++cnt) {
      for (int mask = 0; mask <= full_mask; ++mask) {
        li cur_dp = dp[par][cnt][mask];
        if (cur_dp == INF) {
          continue;
        }
        for (int s = mask; s > 0; s = (s - 1) & mask) {
          li prod = prods[s];
          if (prod <= k) {
            relax_min(dp[par ^ 1][cnt + 1][mask ^ s], cur_dp + costs[i]);
          }
        }
      }
    }
    par ^= 1;
  }
  li res = INF;
  for (int cnt = 0; cnt <= primes.size(); ++cnt) {
    li cur_dp = dp[par][cnt][0];
    if (cur_dp == INF) {
      continue;
    }
    relax_min(res, cnt * cur_dp);
  }
  if (res == INF) {
    res = -1;
  }
  cout << res << "\n";
}
