Description

花猫有一个长度为 $n$ 的序列 $A$ 和另一个长度为 $m$ 的序列 $B$。你可以进行若干次以下操作：

• 选择两个整数 $i$ 和 $j$，满足 $1\le i\le n$，$1\le j\le m$ 且 $B_j \mid A_i$，然后将 $A_i$ 变为 $\frac{A_i}{B_j}$。

注意：$A$ 和 $B$ 中的每个元素都可以选择并被操作多次。

最终要使得 $A$ 中的元素都相等，请求出最少的操作次数；若无解，输出 -1。

Input Format

第一行两个正整数 $n$ 和 $m$。

第二行 $n$ 个正整数表示序列 $A$。

第三行 $m$ 个正整数表示序列 $B$。

Output Format

输出一个整数表示最少的操作次数；若无解，输出 -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

本题采用捆绑测试。

对于所有数据，$1\le n,m\le5\times10^5$，$1\le A_i,B_i\le5\times10^5$。