Equalize Sequence by Dividing with Factors

You are given two sequences: an integer sequence \(A\) of length \(n\) and another integer sequence \(B\) of length \(m\). You can perform the following operation arbitrarily many times:

• Choose two integers \(i\) and \(j\) (\(1\le i\le n\) and \(1\le j\le m\)) such that \(B_j\) divides \(A_i\). Then, update \(A_i\) to \(\displaystyle \frac{A_i}{B_j}\).

Note: Each element in \(A\) and \(B\) may be used repeatedly in the operations.

Your task is to make all elements of \(A\) equal by performing a sequence of such operations. Determine the minimum total number of operations required. If it is impossible to achieve, output -1.

Explanation: Essentially, for each element \(A_i\), you can divide it by any \(B_j\) (if \(B_j\mid A_i\)), thereby removing some prime factors. Notice that the elements of \(B\) (which may be composite) allow you to remove several prime factors at once. However, if some prime factor in \(A_i\) does not appear in any element of \(B\), then it cannot be removed and must appear in the final equal value of every \(A_i\>. This leads to necessary conditions for the possibility of the transformation.

The challenge is to decide which factors to remove from each \(A_i\) (and how many times) so that all final values become equal while minimizing the total number of division operations. Formally, if we denote the prime factorization of \(A_i\) (with respect to the primes that appear in \(B\)) as \(A_i = X \times Q_i\) and we want the final value to be \(X\) (or more generally, some \(Y\) that divides every \(A_i\)), then for each \(A_i\) we must choose a sequence of coin-like operations (each coin corresponding to an element of \(B\) with its prime factorization) whose product is \(Q_i\).

You are to compute the minimum number of operations summed over all \(A_i\) needed to achieve the equalization, or output \( -1 \) if no such sequence of operations exists.

inputFormat

The first line contains two integers \(n\) and \(m\) \( (1\le n, m\le ? )\) representing the lengths of sequences \(A\) and \(B\) respectively.

The second line contains \(n\) integers representing the sequence \(A\): \(A_1, A_2, \ldots, A_n\).

The third line contains \(m\) integers representing the sequence \(B\): \(B_1, B_2, \ldots, B_m\).

outputFormat

Output a single integer, the minimum total number of operations needed to make all elements of \(A\) equal, or \( -1 \) if it is impossible.

sample

2 2
12 18
2 6

3