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.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.Map.Entry;

public class TaskD {

	public FasterScanner mFScanner;
	public PrintWriter mOut;
	HashSet<Integer> badPrimesSet;
	HashMap<Integer, Boolean> mMem;

	public TaskD() {
		mFScanner = new FasterScanner();
		mOut = new PrintWriter(System.out);
	}

	public void solve() {
		int n, m;
		int i;
		int array[];
		int badPrimes[];
		int gcd;

		n = mFScanner.nextInt();
		m = mFScanner.nextInt();
		array = mFScanner.nextIntArray(n);
		badPrimes = mFScanner.nextIntArray(m);
		badPrimesSet = new HashSet<>();
		mMem = new HashMap<>();

		for (i = 0; i < m; i++)
			badPrimesSet.add(badPrimes[i]);

		boolean status;

		while (true) {
			int last = -1;
			int lastGcd = -1;
			gcd = array[0];

			for (i = 0; i < n && gcd != 1; i++) {
				gcd = gcd(gcd, array[i]);
				status = shouldDivideByGCD(gcd);
				if (status) {
					last = i;
					lastGcd = gcd;
				}
			}

			if (last != -1) {

				for (i = 0; i <= last; i++)
					array[i] /= lastGcd;

			} else {
				break;
			}
		}

		int res = 0;

		for (i = 0; i < n; i++) {
			res += count(array[i]);
		}

		mOut.println(res);
	}

	public int count(int num) {
		int res = 0;
		int key;
		HashMap<Integer, Integer> factors;

		factors = getFactors(num);

		for (Entry<Integer, Integer> entry : factors.entrySet()) {
			key = entry.getKey();

			if (badPrimesSet.contains(key)) {
				res -= entry.getValue();
			} else {
				res += entry.getValue();
			}
		}

		return res;
	}

	public HashMap<Integer, Integer> getFactors(int num) {
		HashMap<Integer, Integer> factors = new HashMap<>();
		int sqrt = (int) Math.sqrt(num);
		int count;

		for (int i = 2; i <= sqrt; i++) {
			if (num % i == 0) {
				count = 0;
				while (num % i == 0) {
					num /= i;
					count++;
				}
				factors.put(i, count);
			}
		}

		if (num != 1) {
			factors.put(num, 1);
		}

		return factors;
	}

	public boolean shouldDivideByGCD(int num) {
		if (mMem.containsKey(num))
			return mMem.get(num);
		
		HashMap<Integer, Integer> factors = new HashMap<>();
		int sqrt = (int) Math.sqrt(num);
		int numBack = num;
		int count;
		int total = 0;

		for (int i = 2; i <= sqrt; i++) {
			if (num % i == 0) {
				count = 0;
				while (num % i == 0) {
					num /= i;
					count++;
				}
				total += count;
				factors.put(i, count);
			}
		}

		if (num != 1) {
			factors.put(num, 1);
			total++;
		}

		int bad = 0;

		for (Entry<Integer, Integer> entry : factors.entrySet()) {
			int key = entry.getKey();
			if (badPrimesSet.contains(key)) {
				bad += entry.getValue();
			}
		}

		int good = total - bad;

		if (good >= bad) {
			mMem.put(numBack, false);
			return false;
		}
		
		mMem.put(numBack, true);
		return true;

	}

	public int gcd(int a, int b) {

		if (b == 0)
			return a;

		return gcd(b, a % b);

	}

	public void flush() {
		mOut.flush();
	}

	public void close() {
		mOut.close();
	}

	public static void main(String[] args) {
		TaskD mSol = new TaskD();
		mSol.solve();
		mSol.flush();
		mSol.close();
	}

	class FasterScanner {
		private InputStream mIs;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public FasterScanner() {
			this(System.in);
		}

		public FasterScanner(InputStream is) {
			mIs = is;
		}

		public int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = mIs.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		public String nextLine() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndOfLine(c));
			return res.toString();
		}

		public String nextString() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public long nextLong() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public int nextInt() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

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

		public boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		public boolean isEndOfLine(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}

		public char[] nextCharArray(int N) {
			int i;
			char[] array;
			String str;

			array = new char[N];

			i = 0;

			str = nextLine();

			for (i = 0; i < N && i < str.length(); i++) {
				array[i] = str.charAt(i);
			}

			return array;
		}

		public char[][] nextChar2DArray(int M, int N) {
			int i;
			char[][] array;

			array = new char[M][N];

			i = 0;

			for (i = 0; i < M; i++) {
				array[i] = nextCharArray(N);
			}

			return array;
		}

		public int[] nextIntArray(int N) {
			int i;
			int[] array;

			array = new int[N];

			i = 0;

			for (i = 0; i < N; i++) {
				array[i] = nextInt();
			}

			return array;
		}

		public int[][] nextInt2DArray(int M, int N) {
			int i;
			int[][] array;

			array = new int[M][N];

			i = 0;

			for (i = 0; i < M; i++) {
				array[i] = nextIntArray(N);
			}

			return array;
		}

		public long[] nextLongArray(int N) {
			int i;
			long[] array;

			array = new long[N];

			i = 0;

			for (i = 0; i < N; i++) {
				array[i] = nextLong();
			}

			return array;
		}

		public long[][] nextLong2DArray(int M, int N) {
			int i;
			long[][] array;

			array = new long[M][N];

			i = 0;

			for (i = 0; i < M; i++) {
				array[i] = nextLongArray(N);
			}

			return array;
		}

		public double[] nextDoubleArray(int N) {
			int i;
			double[] array;

			array = new double[N];

			for (i = 0; i < N; i++) {
				array[i] = nextDouble();
			}

			return array;
		}

		public double[][] nextDouble2DArray(int M, int N) {
			int i;
			double[][] array;

			array = new double[M][N];

			for (i = 0; i < M; i++) {
				array[i] = nextDoubleArray(N);
			}

			return array;
		}

	}
}