Bob is learning a new data normalization technique. He has an array of data values ~A~ of size ~n~, and a list of special prime numbers ~B~ of size ~m~.

For any pair of values ~(x, y)~, the normalized value is calculated using the following algorithm:

def normalize(x, y, B[]):
    while exists p in B such that (x % p == 0) and (y % p == 0):
        x = x / p
        y = y / p
    return x + y

Fascinated by how this technique works, Bob challenges you to calculate the total sum of the normalized values for all possible pairs ~(a_i, a_j)~ where ~1 \le i < j \le n~.

Input

The first line contains two integers ~n~ and ~m~ (~2 \le n \le 5 \cdot 10^5~, ~1 \le m \le 10^5~) — the number of data values and the number of special primes.

The second line contains ~n~ integers ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le 2\cdot 10^6~) — the data values.

The third line contains ~m~ distinct integers ~b_1, b_2, \ldots, b_m~ (~1 \le b_i \le 2\cdot 10^6~, all ~b_i~ are prime numbers) — the list of special primes.

Output

Print a single integer — the sum of normalized values for all pairs.

Sample Input 1

3 2
3 6 8
2 3

Sample Output 1

21

Sample Input 2

5 2
2 4 6 8 10
2 3

Sample Output 2

57

Notes

In the example above, the set of special primes is ~B = \{2, 3\}~. The pairs are normalized as follows:

• Pair ~(3, 6)~: The common prime factor is ~3~. Since ~3 \in B~, we divide both by 3 to get ~(1, 2)~. Result: ~1 + 2 = 3~.

• Pair ~(3, 8)~: The greatest common divisor is 1. No reduction is performed. Result: ~3 + 8 = 11~.

• Pair ~(6, 8)~: The common prime factor is ~2~. Since ~2 \in B~, we divide both by 2 to get ~(3, 4)~. Result: ~3 + 4 = 7~.

Total sum: ~3 + 11 + 7 = 21~.