您有一个正整数数组 a[1]、a[2]、...、a[n] 和一组坏素数 b1、b2、...、bm。集合b中未出现的素数被认为是好的素数。数组 a 的美妙之处在于 $$\sum_{i=1}^{n} f(a[i])$$ 之和,其中函数 f(s) 确定如下:
- f(1) = 0;
- 假设 p 是 s 的最小素因数。如果 p 是一个好的素数,则 $$f(s) = f\left(\frac{s}{p}\right) + 1$$,否则 $$f(s) = f\left(\frac{s}{p}\right) - 1$$。
您可以执行任意(可能为零)次数的操作来改进数组 a。改进的操作是以下操作顺序:
- 选择一些数字 r (1 ≤ r ≤ n) 并计算值 g = GCD(a[1], a[2], ..., a[r])。
- 应用分配:$$a[1] = \frac{a[1]}{g}$$、$$a[2] = \frac{a[2]}{g}$$、...、$$a[r] = \frac{a[r]}{g}$$。
你能得到的阵法最大美感是多少?
输入
第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 5000),显示数组中有多少个数字以及有多少个坏素数。
第二行包含 n 个空格分隔的整数 a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 109) — 数组 a。第三行包含 m 个空格分隔的整数 b1, b2, ..., bm (2 ≤ b1 < b2 < ... < bm ≤ 109) — 坏素数的集合。
输出
打印一个整数——问题的答案。
示例
输入 #1
5 2 4 20 34 10 10 2 5
输出 #1
-2
输入 #2
4 5 2 4 8 16 3 5 7 11 17
输出 #2
10
注意
请注意,问题的答案可能是否定的。
GCD(x1, x2, ..., xk) 是除以每个 xi 的最大正整数。