CF402D.Upgrading Array

You have an array of positive integers a[1], a[2], ..., a[n] and a set of bad prime numbers _b_1, _b_2, ..., b__m. The prime numbers that do not occur in the set b are considered good. The beauty of array a is the sum , where function f(s) is determined as follows:

• f(1) = 0;
• Let's assume that p is the minimum prime divisor of s. If p is a good prime, then , otherwise .

You are allowed to perform an arbitrary (probably zero) number of operations to improve array a. The operation of improvement is the following sequence of actions:

• Choose some number r (1 ≤ r ≤ n) and calculate the value g = GCD(a[1], a[2], ..., a[r]).
• Apply the assignments: , , ..., .

What is the maximum beauty of the array you can get?

你有一个正整数数组 $a[1],\ a[2],\ \dots,\ a[n]$ 和一个坏质数集合 $b_1,\ b_2,\ \dots,\ b_m$。不在集合 $b$ 中出现的质数被视为好质数。数组 $a$ 的“美值”定义为和式
，
其中函数 $f(s)$ 定义如下：

• $f(1) = 0$；
• 设 $p$ 是 $s$ 的最小质因子。若 $p$ 是好质数，则
  ，
  否则
  。

你可以执行任意次（可能为零次）操作来改进数组 $a$。一次改进操作按如下步骤进行：

• 选择某个下标 $r$（满足 $1 \le r \le n$），并计算 $g = \gcd(a[1],\ a[2],\ \dots,\ a[r])$；
• 执行赋值操作：
  ，
  ，
  $\dots$，
  。

你能得到的数组最大美值是多少？

The first line contains two integers n and m (1 ≤ n, m ≤ 5000) showing how many numbers are in the array and how many bad prime numbers there are.

The second line contains n space-separated integers a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 109) — array a. The third line contains m space-separated integers _b_1, _b_2, ..., b__m (2 ≤ _b_1 < _b_2 < ... < b__m ≤ 109) — the set of bad prime numbers.

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 5000$），分别表示数组中数字的个数以及坏质数的个数。

第二行包含 $n$ 个以空格分隔的整数 $a[1],\ a[2],\ ..., \ a[n]$（$1 \leq a[i] \leq 10^9$）—— 数组 $a$。
第三行包含 $m$ 个以空格分隔的整数 $b_1,\ b_2,\ ..., \ b_m$（$2 \leq b_1 < b_2 < \ ... \ < b_m \leq 10^9$）—— 坏质数集合。

Print a single integer — the answer to the problem.

输出一个整数——该问题的答案。

Note that the answer to the problem can be negative.

The GCD(_x_1, _x_2, ..., x__k) is the maximum positive integer that divides each x__i.

注意：本题的答案可能为负数。

GCD(_x_₁, _x_₂, ..., x__k) 是能整除每个 _x__i 的最大正整数。