← 返回题目列表

Codeforces · 402/D

D. 升级阵列

中文机器翻译题面 查看原题

您有一个正整数数组 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 的最大正整数。