Background

Is it necessary to connect the backgrounds of all contest problems together.

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."

Problem Description

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.

Input Format

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 Format

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

4 5
16 24 28 36
11 4 7 3 2

6

2 3
11 13
13 1 11

2

2 2
2 3
4 5

-1

Hint

This problem uses bundled tests.

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