A9438 | 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?

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]<=10^{9}$ ) — array $a$ . The third line contains $m$ space-separated integers $b_{1},b_{2},...,b_{m}$ ( $2<=b_{1}<b_{2}<...<b_{m}<=10^{9}$ ) — the set of bad prime numbers.

Print a single integer — the answer to the problem.