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.
/**
 * @author derrick20
 */
import java.io.*;
import java.util.*;

public class UpgradingArray {
    public static void main(String[] args) throws Exception {
        FastScanner sc = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);

//        System.out.println("5000 1");
//        for (int i = 0; i < 5000; i++) {
//            System.out.print((int) 1e9 + " ");
//        }
//        System.out.println();
//        System.out.println(3);
        long start = System.currentTimeMillis();
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] a = new int[N];
        int[] gPrefix = new int[N];
        int g = 0;
        for (int i = 0; i < N; i++) {
            a[i] = sc.nextInt();
            g = gcd(a[i], g);
            gPrefix[i] = g;
        }

        HashSet<Integer> bad = new HashSet<>();
        for (int i = 0; i < M; i++) {
            bad.add(sc.nextInt());
        }

        boolean[] isPrime = new boolean[31623];
        ArrayList<Integer> primes = new ArrayList<>();
        for (int i = 2; i < isPrime.length; i++) {
            if (!isPrime[i]) {
                primes.add(i);
                for (int j = i; j < isPrime.length; j += i) {
                    isPrime[j] = true;
                }
            }
        }

        int[] a2 = new int[N];
        int gDelta = 1;
        for (int r = N - 1; r >= 0; r--) {
            // factorize this value, see whether it has more bad than good
            int val = gPrefix[r] / gDelta;
            int netBad = 0;
            int curr = val;
            for (int i : primes) {
                if (i * i > curr) break;
                if (curr % i == 0) {
                    int exp = 0;
                    while (curr % i == 0) {
                        curr /= i;
                        exp++;
                    }
                    netBad += exp * (bad.contains(i) ? 1 : -1);
                }
            }
            if (curr > 1) {
                netBad += (bad.contains(curr) ? 1 : -1);
            }
            if (netBad > 0) {
                // then it's worthwhile!
                gDelta *= val;
            }
            a2[r] = a[r] / gDelta;
        }
//        System.out.println(Arrays.toString(a2));

        int ans = 0;
        for (int k = 0; k < N; k++) {
            int val = a2[k];
            int curr = val;
            for (int i : primes) {
                if (i * i > curr) break;
                if (curr % i == 0) {
                    int exp = 0;
                    while (curr % i == 0) {
                        curr /= i;
                        exp++;
                    }
                    ans -= exp * (bad.contains(i) ? 1 : -1);
                }
            }
            if (curr > 1) {
                ans -= (bad.contains(curr) ? 1 : -1);
            }
        }
        out.println(ans);
//        out.println((System.currentTimeMillis() - start) / 1000.0);
        out.close();
    }

    static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    static class FastScanner {
        private int BS = 1<<16;
        private char NC = (char)0;
        private byte[] buf = new byte[BS];
        private int bId = 0, size = 0;
        private char c = NC;
        private double cnt = 1;
        private 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);
            }
        }

        private char getChar(){
            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 int[] nextInts(int N) {
            int[] res = new int[N];
            for (int i = 0; i < N; i++) {
                res[i] = (int) nextLong();
            }
            return res;
        }

        public long[] nextLongs(int N) {
            long[] res = new long[N];
            for (int i = 0; i < N; i++) {
                res[i] = nextLong();
            }
            return res;
        }

        public long nextLong() {
            cnt=1;
            boolean neg = false;
            if(c==NC)c=getChar();
            for(;(c<'0' || c>'9'); c = getChar()) {
                if(c=='-')neg=true;
            }
            long res = 0;
            for(; c>='0' && c <='9'; c=getChar()) {
                res = (res<<3)+(res<<1)+c-'0';
                cnt*=10;
            }
            return neg?-res:res;
        }

        public double nextDouble() {
            double cur = nextLong();
            return c!='.' ? cur:cur+nextLong()/cnt;
        }

        public String next() {
            StringBuilder res = new StringBuilder();
            while(c<=32)c=getChar();
            while(c>32) {
                res.append(c);
                c=getChar();
            }
            return res.toString();
        }

        public String nextLine() {
            StringBuilder res = new StringBuilder();
            while(c<=32)c=getChar();
            while(c!='\n') {
                res.append(c);
                c=getChar();
            }
            return res.toString();
        }

        public boolean hasNext() {
            if(c>32)return true;
            while(true) {
                c=getChar();
                if(c==NC)return false;
                else if(c>32)return true;
            }
        }
    }
}