P9589 "PFLOI R1" PFL Division

[Is it necessary to connect the backgrounds of all contest problems together](https://www.luogu.com.cn/paste/enzfvjum). Just like that, the door to a new world opened to them... "Meow!" A cute calico cat greeted them. "Did you just arrive here?" "Mm." "I'll show you around. After all, I'm so cute!" "..." The calico cat suddenly stopped, looked over the sequence in its hands, and then smiled again: "But you have to answer my question first."

The calico cat has a sequence $A$ of length $n$ and another sequence $B$ of length $m$. You may perform the following operation any number of times: - Choose two integers $i$ and $j$ such that $1 \le i \le n$, $1 \le j \le m$, and $B_j \mid A_i$, then change $A_i$ to $\frac{A_i}{B_j}$. **Note**: Each element in $A$ and $B$ can be chosen and **operated on multiple times**. In the end, make all elements in $A$ equal. Please output the minimum number of operations. If there is no solution, output `-1`.

The first line contains two positive integers $n$ and $m$. The second line contains $n$ positive integers representing sequence $A$. The third line contains $m$ positive integers representing sequence $B$.

Output one integer representing the minimum number of operations. If there is no solution, output `-1`.

**This problem uses bundled tests**. | Subtask ID | Special Property | Score | | :----------: | :----------: | :-----: | | $1$ | All elements in $A$ are equal. | $5$ | | $2$ | $n = 2$ | $15$ | | $3$ | $n, m \le 10^3$ | $20$ | | $4$ | $n, m \le 10^4$ | $20$ | | $5$ | None. | $40$ | For all data, $1 \le n, m \le 5 \times 10^5$, $1 \le A_i, B_i \le 5 \times 10^5$. Translated by ChatGPT 5