题目背景

有必要把所有比赛题的背景连在一起。

就这样，新世界的大门向它们敞开了……

“喵！”一只可爱的花猫向它们问好。

“你们刚来到这？”

“嗯。”

“我带你们去转转吧，谁叫我这么可爱呢！”

“……” 花猫突然止住，打量一番手中的序列，俶尔又微笑着说：

“但你们要先答出我的问题哦。”

题目描述

花猫有一个长度为 $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。

输入格式

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

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

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

输出格式

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

提示

本题采用捆绑测试。

子任务编号	特殊性质	分值
$1$	$A$ 中所有元素相等	$5$
$2$	$n=2$	$15$
$3$	$n,m\le10^3$	$20$
$4$	$n,m\le10^4$
$5$	无	$40$

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