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 java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.StringTokenizer;

/**
 * @author Jens Staahl
 */

public class Prac {

	// some local config
	// static boolean test = false ;
	private boolean test = System.getProperty("ONLINE_JUDGE") == null;
	static String testDataFile = "testdata.txt";
	// static String testDataFile = "testdata.txt";
	private static String ENDL = "\n";
	// Just solves the acutal kattis-problem
	ZKattio io;
	int maxn = (int)Math.sqrt((int) (1e9));
	int[] ps;
	{
		boolean[] primes = new boolean[maxn];
		Arrays.fill(primes, true);
		primes[0] = primes[1] = false;
		int psc = 0;
		for (int i = 2; i < primes.length; ++i) {
			if (primes[i]) {
				psc++;
				for (int j = 2 * i; j < primes.length; j += i) {
					primes[j] = false;
				}
			}
		}
		ps = new int[psc];
		for (int i = 0, j = 0; i < primes.length; ++i) {
			if (primes[i]) {
				ps[j++] = i;
			}
		}
	}
	
	private void solve() throws Throwable {
		io = new ZKattio(stream);
		int n = io.getInt(), m = io.getInt();
		
		HashSet<Integer> bad = new HashSet<>();
		int[] a = new int[n];
		List[] primes = new List[n];
		for (int i = 0; i < n; i++) {
			primes[i] = new ArrayList<>();
		}
		for (int i = 0; i < n; i++) {
			a[i] = io.getInt();
		}
		for (int i = 0; i < m; i++) {
			bad.add(io.getInt());
		}
		int totScore = 0;
		for (int i = 0; i < n; i++) {
			int p = 0;
			while(a[i] > 1 && p < ps.length){
				while(a[i] % ps[p] == 0) {
					primes[i].add(ps[p]);
					a[i] /= ps[p];
				}
				p++;
			}
			if(a[i] > 1) {
				primes[i].add(a[i]);
			}
			Collections.sort(primes[i]);
			for (int j = 0; j < primes[i].size(); j++) {
				if(bad.contains(primes[i].get(j))) {
					totScore --;
				} else {
					totScore ++;
				}
			}
		}

		int startP = primes[0].size();
		boolean[] in = new boolean[startP];
		Arrays.fill(in, true);
		int[] delete = new int[n];
		Arrays.fill(delete, -(1 << 28));

		for (int i = 0; i < n; i++) {
			int pp = 0;
			int score = 0;
			for (int j = 0; j < primes[0].size(); j++) {
				if (pp < primes[i].size()) {

					int origPrime = (Integer) primes[0].get(j);
					int curPrime = (int) primes[i].get(pp);
					while (pp < primes[i].size()) {
						curPrime = (int) primes[i].get(pp);
						if (curPrime >= origPrime) {
							break;
						}
						pp++;
					}
					if (in[j] && curPrime != origPrime) {
						in[j] = false;
					} else if (in[j]) {
						score += bad.contains(origPrime) ? -1 : 1;
						pp++;
					} else {
						in[j] = false;
					}
				} else {
					in[j] = false;
				}
			}
			delete[i] = -score;
		}
		for (int i = delete.length - 1 ; i >= 0; i--) {
			int donothing = 0;
			int useMy = delete[i];
			int useRight = donothing;
			if(i < delete.length-1) {
				useRight = delete[i+1];
			}
			delete[i] = Math.max(donothing, Math.max(useMy, useRight));
		}
		int fix = 0;
		for (int i = 0; i < delete.length; i++) {
			fix += delete[i];
		}
		System.out.println(totScore + fix);
	}

	public static void main(String[] args) throws Throwable {
		new Prac().solve();
	}

	public Prac() throws Throwable {
		if (test) {
			stream = new FileInputStream(testDataFile);
		}
	}

	InputStream stream = System.in;
	PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));// outStream

	public class ZKattio extends PrintWriter {
		public ZKattio(InputStream i) {
			super(new BufferedOutputStream(System.out));
			r = new BufferedReader(new InputStreamReader(i));
		}

		public ZKattio(InputStream i, OutputStream o) {
			super(new BufferedOutputStream(o));
			r = new BufferedReader(new InputStreamReader(i));
		}

		public boolean hasMoreTokens() {
			return peekToken() != null;
		}

		public int getInt() {
			return Integer.parseInt(nextToken());
		}

		public double getDouble() {
			return Double.parseDouble(nextToken());
		}

		public long getLong() {
			return Long.parseLong(nextToken());
		}

		public String getWord() {
			return nextToken();
		}

		private BufferedReader r;
		private String line;
		private StringTokenizer st;
		private String token;

		private String peekToken() {
			if (token == null)
				try {
					while (st == null || !st.hasMoreTokens()) {
						line = r.readLine();
						if (line == null)
							return null;
						st = new StringTokenizer(line);
					}
					token = st.nextToken();
				} catch (IOException e) {
				}
			return token;
		}

		private String nextToken() {
			String ans = peekToken();
			token = null;
			return ans;
		}
	}
	// System.out;

}