Professional layer
Contest: Codeforces Round 534 (Div. 1)
Difficulty rating: 3100
Tags: bitmasks, dp

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 \cdot y$$$ seconds.

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

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

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

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

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

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Example input:
3 6
30 30 30
100 4 5

Example output:
18

Example input:
1 1000000
1
100

Example output:
0

Editorial:
We supposed this as the author solution:
Let's find $$$gcd$$$ and factorize it. $$$gcd = p_1^{\alpha_1} \cdot \ldots \cdot p_m^{\alpha_m}$$$, where $$$p_i$$$ $$$i$$$-th prime number in factorization ($$$p_i < p_{i+1}$$$) and $$$\alpha_i > 0$$$ — number of occurrences of this prime. It's clear, that $$$m \leq 11$$$ in our constraints, because $$$a_i \leq 10^{12}$$$. Obviously, that in optimal answer is always best to divide set of our primes in subsets and distribute these subsets between array numbers and divide each number $$$a_i$$$ by product of all primes (with $$$a_i$$$ powers) in corresponding subset.
Also clear, that we are interested in only vector of powers of primes of $$$gcd$$$, other primes in a factorization of $$$a_i$$$ we can ignore, but we need to be cautious about costs, so, we can left the cheapest $$$m$$$ numbers with the same prime-vector. After this compression we will left at most $$$M = 12000$$$ numbers. We can get this estimation by this point: maximum numbers after compression we can reach if all primes are small as possible and $$$\alpha_i = 1$$$ for all $$$i$$$. Hence, we have at most $$$11$$$ possibilities and can easily brute all of them. Also, after compression, let's calculate vector $$$best(mask)$$$ - best $$$m$$$ numbers by cost to cover set of primes corresponding to $$$mask$$$. We can do it easily in $$$O(M \cdot 2^m \cdot m)$$$.
Now let's fix a partition of our set of primes into subsets. Well known, that the number of partitions is equal to $$$B_m$$$, where $$$B_i$$$ — $$$i$$$-th Bell number. Now, we want to update the current answer. We need to do it by value $$$x \cdot y$$$, where $$$x$$$ is number of subsets in the partition (we already know it) and $$$y$$$ is minimum cost to distribute our subsets between array numbers. Let's consider all indices $$$i$$$ for subset $$$mask$$$ which we can match with this $$$mask$$$ by constraint "divisor is at most k". We will get the bipartite graph with weighted right part (part with indices) and our purpose is to find perfect matching with minimal cost of used vertices in the right part. We can solve this problem with Kuhn algorithm greedily — we can sort right part in not ascending order and do all iterations in this order. It's correct, because we can consider transversal matroid with elements in right part and apply greed Rado-Edmonds theorem. Now we need just to figure out, that we can build this graph using precalced $$$best(mask)$$$, because we are interested only in at most $$$m$$$ best indices for the particular vertex in the left part. So, we will have graph with $$$O(x^2)$$$ edges and $$$O(x)$$$ size of the left part. Kuhn algorithm will be work in $$$O(x^3)$$$ (even we do the algorithm in right part with size $$$O(x^2)$$$) if we clear $$$used$$$ array carefully — only after increasing of the current matching. Summing up $$$x^3$$$ over all partitions of $$$11$$$ elements we will get $$$\sim 10^8$$$ operations.
P. S. Solutions that were passed by participants during the contest used same ideas about the compression. But instead of minimal matching we will use dynamic programming approach. Let's denote $$$dp(mask, i)$$$ - minimal cost to correctly cover set of primes corresponding to $$$mask$$$ using exactly $$$i$$$ divisions. To calculate it let's precalc $$$best'(i)$$$ (inversion of $$$best(mask)$$$) — $$$m$$$ masks for which $$$i$$$-th number of the array is one of $$$m$$$ best. Using this helped data we can calculate our $$$dp(mask, i)$$$. For this, we can iterate over all numbers and try to update all states where we can use our $$$best'(i)$$$ masks. It will be work in $$$O(m^2 \cdot 3^m)$$$ and all algorithm will be work in $$$O(M \cdot 2^m \cdot m + m^2 \cdot 3^m)$$$