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.util.*;
import java.io.*;
    
    public class B {
        public static long time = 0;
    
        public static void main(String[] args) throws Exception {
            time = System.currentTimeMillis();
    
            IN = System.in;
            OUT = System.out;
            in = new BufferedReader(new InputStreamReader(IN));
            out = new PrintWriter(OUT, FLUSH);
            solveOne();
            out.flush();
        }
        public static IntL primes = NT.sieve(35000);
        public static ArrayList<Long> primeFactors(long n1){
            ArrayList<Long> fin = new ArrayList<>();
            for (long e: primes){
                for (;n1 % e == 0;){
                    fin.add(e);
                    n1 /= e;
                }
            }
            if (n1 > 1) fin.add(n1);
            return fin;
        }
    
        public static void solveOne() throws Exception {
            int elementNumber = ni();
            int badPrimeNumber = ni();
            long[] l1 = nll(elementNumber);
            long[] badPrime = nll(badPrimeNumber);
            IntL primes = NT.sieve(35000);
            ArrayList<Long>[] primeFactors = new ArrayList[elementNumber];
            for (int i =0 ;i < primeFactors.length; i++){
                primeFactors[i] = primeFactors(l1[i]);
//              px(primeFactors[i]);
            }
//          px(primes.size);
            int[] dpList = new int[elementNumber + 10];
            long curGCD = l1[0];
            for (int i =0; i < elementNumber; i++){
                curGCD = NT.gcd(curGCD, l1[i]);
                
                int goodNo = 0;
                int badNo = 0;
                for (long e: primeFactors(curGCD) ){
                    if (Arrays.binarySearch(badPrime, e) >= 0){
                        badNo++;
                    }
                    else {
                        goodNo++;
                    }
                }
                int unitChange = badNo - goodNo;
//              px(curGCD, unitChange);
                for (int j = 0; j <= i;j++){
                    int curChange = (i + 1 - j) * unitChange;
                    int newTotalChange = dpList[j] + curChange;
                    dpList[i + 1] = Math.max(newTotalChange, dpList[i + 1]);
                }
            }
            int total = 0;
            for (int i =0; i < elementNumber; i++){
                for (long f: primeFactors[i]){
                    if (Arrays.binarySearch(badPrime, f) >= 0){
                        total--;
                    }
                    else {
                        total++;
                    }
                }
            }
            int bestChange = 0;
            for (int e: dpList){
                bestChange = Math.max(bestChange, e);
            }
//          px(dpList);
//          px(total, bestChange);
            pn(total + bestChange);
            
        }
        
    
        public static void solveTwo() throws Exception {
            
        }
    
        public static void solveThree() throws Exception {
    
        }
    
        public static BufferedReader in;
        public static StringTokenizer st;
        public static InputStream IN;
        public static OutputStream OUT;
    
        public static String nx() throws Exception {
            for (; st == null || !st.hasMoreTokens();) {
                String k1 = in.readLine();
                if (k1 == null) return null;
                st = new StringTokenizer(k1);
            }
            return st.nextToken();
        }
    
        public static int ni() throws Exception {
            return Integer.parseInt(nx());
        }
    
        public static long nl() throws Exception {
            return Long.parseLong(nx());
        }
    
        public static double nd() throws Exception {
            return Double.parseDouble(nx());
        }
    
        private static long[] nll(int n1) throws Exception {
            long[] l1 = new long[n1];
            for (int i = 0; i < n1; i++) {
                l1[i] = nl();
            }
            return l1;
        }
    
        public static void px(Object... l1) {
            System.out.println(Arrays.deepToString(l1));
        }
    
        public static boolean FLUSH = false;
        public static PrintWriter out;
    
        public static void p(Object... l1) {
            for (int i = 0; i < l1.length; i++) {
                if (i != 0) out.print(' ');
                out.print(l1[i].toString());
            }
        }
    
        public static void pn(Object... l1) {
            for (int i = 0; i < l1.length; i++) {
                if (i != 0) out.print(' ');
                out.print(l1[i].toString());
            }
            out.println();
        }
    
        public static void pn(Collection l1) {
            boolean first = true;
            for (Object e : l1) {
                if (first) first = false;
                else out.print(' ');
                out.print(e.toString());
            }
            out.println();
        }
    
        private static class IntL implements Iterable<Integer> {
            public int[] cont = null;
            public int size = 0;
    
            public IntL(int initialCapacity) {
                this.cont = new int[initialCapacity];
            }
    
            public IntL() {
                this(5);
            }
    
            public void add(int e) {
                if (size == cont.length) {
                    cont = Arrays.copyOf(cont, ((cont.length * 3) >> 1) + 1);
                }
                cont[size++] = e;
            }
    
            @Override
            public String toString() {
                StringBuilder fin = new StringBuilder();
                fin.append('{');
                for (int i = 0; i < size; i++) {
                    if (i != 0) fin.append(", ");
                    fin.append(cont[i]);
                }
                fin.append('}');
                return fin.toString();
            }
    
            @Override
            public Iterator<Integer> iterator() {
                return new It();
            }
    
            public class It implements Iterator<Integer> {
                private int ptr = 0;
    
                @Override
                public boolean hasNext() {
                    if (ptr < size) return true;
                    return false;
                }
    
                @Override
                public Integer next() {
                    return cont[ptr++];
                }
    
                @Override
                public void remove() {}
            }
        }
    
        private static class NT {
            public static IntL sieve(int n1) {
                IntL fin = new IntL();
                boolean[] l1 = new boolean[n1 + 1];
                int last = 0;
                for (int m = 2; m * m <= n1; m++) {
                    if (!l1[m]) {
                        fin.add(m);
                        for (int k = m * m; k <= n1; k += m)
                            l1[k] = true;
                    }
                    last = m;
                }
                for (int m = last + 1; m <= n1; m++) {
                    if (!l1[m]) fin.add(m);
                }
                return fin;
            }
    
            public static long gcd(long n1, long n2) {
                return n2 == 0 ? n1 : gcd(n2, n1 % n2);
            }
        }
    
    }
