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 B2 {
    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;
    }

    static long[] badPrime;

    public static int score(long n1) {
        int fin = 0;
        for (long e : primes) {
            for (; n1 % e == 0;) {
                if (Arrays.binarySearch(badPrime, e) >= 0) {
                    fin--;
                } else {
                    fin++;
                }
                n1 /= e;
            }
        }
        if (n1 > 1) {
            if (Arrays.binarySearch(badPrime, n1) >= 0) {
                fin--;
            } else {
                fin++;
            }
        }
        return fin;
    }

    public static void solveOne() throws Exception {
        int elementNumber = ni();
        int badPrimeNumber = ni();
        long[] l1 = nll(elementNumber);
        badPrime = nll(badPrimeNumber);
        // 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 unitChange = -score(curGCD);
            // 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++) {
            total += score(l1[i]);
        }
        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);
        }
    }

}
