You have an array of positive integers a[1], a[2], ..., a[n] and a set of bad prime numbers b1, b2, ..., bm. The prime numbers that do not occur in the set b are considered good. The beauty of array a is the sum <image>, 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 <image>, otherwise <image>. 



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: <image>, <image>, ..., <image>. 



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

Input

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 b1, b2, ..., bm (2 ≤ b1 < b2 < ... < bm ≤ 109) — the set of bad prime numbers.

Output

Print a single integer — the answer to the problem.

Examples

Input

5 2
4 20 34 10 10
2 5


Output

-2


Input

4 5
2 4 8 16
3 5 7 11 17


Output

10

Note

Note that the answer to the problem can be negative.

The GCD(x1, x2, ..., xk) is the maximum positive integer that divides each xi.
import static java.lang.Math.*; 

import java.io.*; 
import java.util.*; 

public class Template {
	BufferedReader in; 
	PrintWriter out;
	StringTokenizer st; 

	String next() {
		while (st==null || !st.hasMoreTokens()) {
			try {
				st = new StringTokenizer(in.readLine());
			} catch (Exception e) {}
		}
		return st.nextToken(); 
	}

	int nextInt() {
		return Integer.parseInt(next()); 
	}

	long nextLong() {
		return Long.parseLong(next());
	}

	double nextDouble() {
		return Double.parseDouble(next());
	}

	int[] a; 
	int n,m; 
	Tree[] t; 
	class Tree {
		int[] le, ri; 
		long[] s; 
		boolean[] all; 

		public Tree(int n) {
	//		a = new int[4 * n]; 
			le = new int[4 * n]; 
			ri = new int[4 * n]; 
			s = new long[4 * n]; 
			all = new boolean[4 * n]; 
		}

		public void update(int p, int v) {
			update(1, 1, n, p, v);
		}

		public void update(int v, int l, int r, int p, int val) {
			if (l > p || r < p) return;
			if (l == r) {
				//a[v] = val; 
				if (val == 1) le[v] = 1; else le[v] = 0; 
				if (val == 1) ri[v] = 1; else ri[v] = 0; 
				if (val == 1) s[v] = 1; else s[v] = 0; 
				if (val == 1) all[v] = true; else all[v] = false; 
				return;
			}
			int m = (l+r) / 2; 
			update(v*2, l, m, p, val);
			update(v*2+1, m+1, r, p, val);
			long sl = s[v*2] - ri[v*2]*(ri[v*2] + 1L)/2; 
			long sr = s[v*2+1] - le[v*2+1]*(le[v*2+1] + 1L)/2; 
			long mid = ri[v*2] + le[v*2+1]; 
			mid = mid * (mid + 1L) / 2; 
			s[v] = sl + sr + mid; 
			all[v] = all[v*2] & all[v*2+1];
			ri[v] = ri[v*2+1] + (all[v*2+1] ? ri[v*2] : 0); 
			le[v] = le[v*2] + (all[v*2] ? le[v*2+1] : 0); 
		}
	}

	int bit(int x, int p) {
		if ((x & (1 << p)) > 0) return 1; else return 0;
	}

	int gcd(int a, int b) {
		if (b == 0) return a; 
		return gcd(b, a % b);
	}

	public void run() throws Exception {
		in = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		Long start = System.currentTimeMillis();
			int n = nextInt(); 
			int m = nextInt(); 
			int[] a = new int[n]; 
			HashSet<Integer> b = new HashSet<Integer>(); 

			for (int i=0; i<n; i++) a[i] = nextInt(); 
			for (int i=0; i<m; i++) b.add(nextInt()); 

			boolean[] pr = new boolean[40000]; 

			int[] primes = new int[5000]; 
			int pcnt=0; 

			for (int i=2; i*i <= 40000; i++) if (pr[i] == false) {
				for (int j=i+i; j<40000; j+=i) pr[j] = true; 
			}

			for (int i=2; i<40000; i++) if (pr[i] == false) primes[pcnt++] = i; 

			//System.err.println(pcnt);

			int[] s = new int[n]; 

			for (int i=0; i<n; i++) {
				int x = a[i]; 
				for (int j=0; j<pcnt && primes[j] * primes[j] <= x; j++) if (x % primes[j] == 0) {
					int k=0; 
					while (x % primes[j] == 0) {
						k++; 
						x/=primes[j]; 
					}
					if (b.contains(primes[j])) s[i]-=k; else s[i]+=k; 
				}

				if (x > 1) {
					if (b.contains(x)) s[i]-=1; else s[i]+=1; 
				}
			}

		//	System.err.println(Arrays.toString(s));

			for (int i=n-1; i>=0; i--) {
				int g = a[0]; 
				for (int j=1; j<=i; j++) g = gcd(g, a[j]);

				int x = g; 
				int ss=0; 

				for (int j=0; j<pcnt && primes[j] * primes[j] <= x; j++) if (x % primes[j] == 0) {
					int k=0; 
					while (x % primes[j] == 0) {
						k++; 
						x/=primes[j]; 
					}
					if (b.contains(primes[j])) ss-=k; else ss+=k; 
				}

				if (x > 1) {
					if (b.contains(x)) ss-=1; else ss+=1; 
				}


				if (ss < 0) {
					for (int j=0; j<=i; j++) {
						s[j] = s[j] - ss; 
						a[j] /= g; 
					}
				}
			}
			
			int ans=0; 
			for (int i=0; i<n; i++) ans+=s[i]; 

			out.println(ans);




			

			


		Long end = System.currentTimeMillis();

		//System.out.println((end - start) / 1000.0);
		out.close(); 
	}

	public static void main(String[] args) throws Exception {
		new Template().run(); 
	}
}                                      