Problem Description

A cute cat has a sequence \( A \) of length \( n \) and another sequence \( B \) of length \( m \). You can perform the following operation multiple times:

• Choose two integers \( i \) and \( j \), satisfying \( 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 selected and operated on multiple times.

The goal is to make all elements in \( A \) equal, and you need to find the minimum number of operations required. If it's impossible, 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 a single integer representing the minimum number of operations required. If it's impossible, output -1.

Sample Input and Output

Sample Input #1

4 5
16 24 28 36
11 4 7 3 2

Sample Output #1

6

Sample Input #2

2 3
11 13
13 1 11

Sample Output #2

2

Sample Input #3

2 2
2 3
4 5

Sample Output #3

-1

Notes

This problem uses subtask scoring.

For all data, \( 1 \le n, m \le 5 \times 10^5 \), \( 1 \le A_i, B_i \le 5 \times 10^5 \).

见题面 Input 部分

见题面 Output 部分