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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Collection;
import java.util.Locale;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		new Thread(null, new Runnable() {
			public void run() {
				try {
					long prevTime = System.currentTimeMillis();
					new Main().run();
					System.err.println("Total time: "
							+ (System.currentTimeMillis() - prevTime) + " ms");
					System.err.println("Memory status: " + memoryStatus());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
		}, "1", 1L << 24).start();
	}

	void run() throws IOException {
		in = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		Object o = solve();
		if (o != null)
			out.println(o);
		out.close();
		in.close();
	}

	int N = 32000;

	private Object solve() throws IOException {
		int[] sieve = build(N);
		int[] primes = primes(sieve);

		int n = ni();
		int m = ni();

		int[] arr = nia(n);
		int[] bad = nia(m);
		
		int[] prime_array = make_dif(arr, sieve, primes, bad);

		int[] gcd = make_gcd(arr);
		int[] dif = make_dif(gcd, sieve, primes, bad);
		for(int i =0;i<dif.length;i++)
			dif[i]*=-1;

		int[] dp = new int[n]; // mejor beneficio, ultimo usado
		for(int i =0;i<n;i++)
			dp[i]= (i+1) * dif[i];
		
		for(int i =n-2;i>=0;i--)
			for(int j =i+1;j<n;j++)
				dp[i]= Math.max(dp[i], (dif[i]-dif[j]) * (i+1) + dp[j]);
		
		int max = 0;
		for(int a : dp)
			max = Math.max(max, a);
		int ret = Math.max(max, 0);
		for(int a : prime_array)
			ret+=a;
			
		return ret;
	}

	private int[] make_dif(int[] arr, int[] sieve, int[] primes, int[] bad) {
		int n = arr.length;
		int[] good_arr = number_primes(arr, sieve, primes);
		int[] bad_arr = number_bad_primes(arr, bad);

		int[] ret = new int[n];
		for (int i = 0; i < n; i++)
			ret[i] = good_arr[i] - 2 * bad_arr[i];

		return ret;
	}

	private int[] number_primes(int[] arr, int[] sieve, int[] primes) {
		int n = arr.length;
		int[] ret = new int[n];
		for (int i = 0; i < n; i++) {
			int aux = arr[i];

			for (int p : primes) {
				if (p * p > aux || aux <= N)
					break;
				while (aux % p == 0) {
					aux /= p;
					ret[i]++;
				}
			}
			if (aux > N) {
				ret[i]++;
			} else {
				ret[i] += sieve[aux];
			}
		}
		return ret;
	}

	private int[] number_bad_primes(int[] arr, int[] bad_primes) {
		int n = arr.length;
		int[] ret = new int[n];
		for (int i = 0; i < n; i++) {
			int aux = arr[i];
			for (int p : bad_primes) {
				while (aux % p == 0) {
					aux /= p;
					ret[i]++;
				}
			}
		}

		return ret;
	}

	private int[] primes(int[] sieve) {
		int count = 0;
		for (int a : sieve)
			if (a == 1)
				count++;
		int[] ret = new int[count];
		int index = 0;
		for (int i = 0; i < sieve.length; i++)
			if (sieve[i] == 1)
				ret[index++] = i;
		return ret;
	}

	private int[] make_gcd(int[] arr) {
		int[] ret = new int[arr.length];
		ret[0] = arr[0];
		for (int i = 1; i < arr.length; i++)
			ret[i] = gcd(ret[i - 1], arr[i]);
		return ret;
	}

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

	private int[] build(int N) {
		int[] ret = new int[N + 1];
		for (int i = 2; i <= N; i++)
			ret[i] = i;
		for (int i = 2; i <= N; i++)
			if (ret[i] == i)
				for (int j = 2; i * j <= N; j++)
					ret[i * j] = Math.min(ret[i * j], i);

		for (int i = 2; i <= N; i++)
			if (ret[i] == i) {
				ret[i] = 1;
			} else {
				ret[i] = 1 + ret[i / ret[i]];
			}
		return ret;
	}

	BufferedReader in;
	PrintWriter out;
	StringTokenizer strTok = new StringTokenizer("");

	String nextToken() throws IOException {
		while (!strTok.hasMoreTokens())
			strTok = new StringTokenizer(in.readLine());
		return strTok.nextToken();
	}

	int ni() throws IOException {
		return Integer.parseInt(nextToken());
	}

	long nl() throws IOException {
		return Long.parseLong(nextToken());
	}

	double nd() throws IOException {
		return Double.parseDouble(nextToken());
	}

	int[] nia(int size) throws IOException {
		int[] ret = new int[size];
		for (int i = 0; i < size; i++)
			ret[i] = ni();
		return ret;
	}

	long[] nla(int size) throws IOException {
		long[] ret = new long[size];
		for (int i = 0; i < size; i++)
			ret[i] = nl();
		return ret;
	}

	double[] nda(int size) throws IOException {
		double[] ret = new double[size];
		for (int i = 0; i < size; i++)
			ret[i] = nd();
		return ret;
	}

	String nextLine() throws IOException {
		strTok = new StringTokenizer("");
		return in.readLine();
	}

	boolean EOF() throws IOException {
		while (!strTok.hasMoreTokens()) {
			String s = in.readLine();
			if (s == null)
				return true;
			strTok = new StringTokenizer(s);
		}
		return false;
	}

	void printRepeat(String s, int count) {
		for (int i = 0; i < count; i++)
			out.print(s);
	}

	void printArray(int[] array) {
		for (int i = 0; i < array.length; i++) {
			if (i > 0)
				out.print(' ');
			out.print(array[i]);
		}
		out.println();
	}

	void printArray(long[] array) {
		for (int i = 0; i < array.length; i++) {
			if (i > 0)
				out.print(' ');
			out.print(array[i]);
		}
		out.println();
	}

	void printArray(double[] array) {
		for (int i = 0; i < array.length; i++) {
			if (i > 0)
				out.print(' ');
			out.print(array[i]);
		}
		out.println();
	}

	void printArray(double[] array, String spec) {
		for (int i = 0; i < array.length; i++) {
			if (i > 0)
				out.print(' ');
			out.printf(Locale.US, spec, array[i]);
		}
		out.println();
	}

	void printArray(Object[] array) {
		boolean blank = false;
		for (Object x : array) {
			if (blank)
				out.print(' ');
			else
				blank = true;
			out.print(x);
		}
		out.println();
	}

	@SuppressWarnings("rawtypes")
	void printCollection(Collection collection) {
		boolean blank = false;
		for (Object x : collection) {
			if (blank)
				out.print(' ');
			else
				blank = true;
			out.print(x);
		}
		out.println();
	}

	static String memoryStatus() {
		return (Runtime.getRuntime().totalMemory()
				- Runtime.getRuntime().freeMemory() >> 20)
				+ "/" + (Runtime.getRuntime().totalMemory() >> 20) + " MB";
	}
}