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.*;
import java.math.BigInteger;
import java.util.*;
 
public class C implements Runnable {
	public static void main (String[] args) {new Thread(null, new C(), "_cf", 1 << 28).start();}
 
	 int index;
	 boolean[] sieve;
	 int[] primes;
	
	public void run() {
		FastScanner fs = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		System.err.println("");
		
		int max = (int)1e5;
        sieve = new boolean[max];
        Arrays.fill(sieve, true);
        sieve[0] = sieve[1] = false;
        primes = new int[max];
        index = 0;
 
        for(int i = 2; i < max; i++) {
            if(!sieve[i]) continue;
            primes[index++] = i;
            for(int j = 2 * i; j < max; j += i) {
                sieve[j] = false;
            }
        }
 
		int n = fs.nextInt(), m = fs.nextInt();
		HashSet<Integer> set = new HashSet<>();
		int[] a = new int[n];
		int[][] costs = new int[n][];
		for(int i = 0; i < n; i++) {
			a[i] = fs.nextInt();
			costs[i] = pf(a[i]);
		}
		for(int i = 0; i < m; i++) set.add(fs.nextInt());
		int[] cost = new int[n];
		int ret = 0;
		for(int i = 0; i < n; i++) {
			for(int e : costs[i]) {
				if(set.contains(e)) cost[i] -= 1;
				else cost[i] += 1;
			}
			ret += cost[i];
		}
		
		int res = ret;
		for(int i = n-1; i >= 0; i--) {
			int nxt = res;
			int g = 0;
			for(int j = i; j >= 0; j--) g = gcd(g, a[j]);
			int[] get = pf(g);
//			System.out.println(g + " " + Arrays.toString(Arrays.copyOfRange(res1, 0, ptr)));
			for(int e : get) {
				int v = set.contains(e) ? -1 : 1;
				nxt -= (i+1)*v;
			}
			if(nxt > res) {
				res = nxt;
				for(int j = i; j >= 0; j--) a[j] /= g;
			}
		}
		out.println(res);
		
		out.close();
	}
	
	int gcd(int a, int b) {
		return b == 0 ? a : gcd(b, a % b);
	}
	
	int find(int key, int[] b) {
		int lo = 0, hi = b.length-1;
		for(int bs = 0; bs < 50 && lo <= hi; bs++) {
			int mid = (lo+hi)/2;
			if(b[mid] > key) hi = mid-1;
			else if(b[mid] < key) lo = mid+1;
			else return mid;
		}
		return -1;
	}
	
	int[] res1 = new int[100];
	int ptr;
	int[] getPrimes(int n) {
		if(BigInteger.valueOf(n).isProbablePrime(1)) {
			int[] res = {n};
			return res;
		}
		int[] res1 = new int[100];
		int ptr = 0;
		int lim = (int)Math.sqrt(n);
		for(int i = 2; i <= lim; i++) {
			if(n % i != 0) continue;
			while(n % i == 0) {
				res1[ptr++] = i;
				n /= i;
			}
		}
		if(n > 1) {
			res1[ptr++] = n;
		}
		res1 = Arrays.copyOfRange(res1, 0, ptr);
		
		return res1;
	}
	
    int[] pf (int n) {
        if(n == 1) return new int[0];
        int[] res = new int[100];
        int ptr = 0;
        int pos = 0;
        int number = n;
        while (number > 1 && pos < index) {
            while (number % primes[pos] == 0) {
                res[ptr++] = (primes[pos]);
                number /= primes[pos];
            }
            pos++;
        }
        if (number > 1) res[ptr++] = (number);
//        System.out.println(n + " = " + pf.toString());
        res = Arrays.copyOfRange(res, 0, ptr);
        return res;
    }
	
	void getPrimes2(int n) {
		ptr = 0;
		int lim = (int)Math.sqrt(n);
		for(int i = 2; i <= lim; i++) {
			if(n % i != 0) continue;
			while(n % i == 0) {
				res1[ptr++] = i;
				n /= i;
			}
		}
		if(n > 1) {
			res1[ptr++] = n;
		}
	}
 
	class FastScanner {
		public int BS = 1<<16;
		public char NC = (char)0;
		byte[] buf = new byte[BS];
		int bId = 0, size = 0;
		char c = NC;
		double num = 1;
		BufferedInputStream in;
 
		public FastScanner() {
			in = new BufferedInputStream(System.in, BS);
		}
 
		public FastScanner(String s) {
			try {
				in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
			}
			catch (Exception e) {
				in = new BufferedInputStream(System.in, BS);
			}
		}
 
		public char nextChar(){
			while(bId==size) {
				try {
					size = in.read(buf);
				}catch(Exception e) {
					return NC;
				}                
				if(size==-1)return NC;
				bId=0;
			}
			return (char)buf[bId++];
		}
 
		public int nextInt() {
			return (int)nextLong();
		}
 
		public long nextLong() {
			num=1;
			boolean neg = false;
			if(c==NC)c=nextChar();
			for(;(c<'0' || c>'9'); c = nextChar()) {
				if(c=='-')neg=true;
			}
			long res = 0;
			for(; c>='0' && c <='9'; c=nextChar()) {
				res = (res<<3)+(res<<1)+c-'0';
				num*=10;
			}
			return neg?-res:res;
		}
 
		public double nextDouble() {
			double cur = nextLong();
			return c!='.' ? cur:cur+nextLong()/num;
		}
 
		public String next() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c>32) {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}
 
		public String nextLine() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c!='\n') {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}
 
		public boolean hasNext() {
			if(c>32)return true;
			while(true) {
				c=nextChar();
				if(c==NC)return false;
				else if(c>32)return true;
			}
		}
		
		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for(int i = 0; i < n; i++) res[i] = nextInt();
			return res;
		}
		
	}
 
}