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 Program {
    public static void main(String[] args) throws IOException {
//        InputStream inputStream = new FileInputStream().open();
        InputStream inputStream = new ConsoleInputStream().open();
//        OutputStream outputStream = new FileOutputStream().open();
        OutputStream outputStream = new ConsoleOutputStream().open();
        new Program().run(inputStream, outputStream, Arrays.asList(args).contains("DEBUG_MODE"));
        outputStream.close();
        inputStream.close();
    }

    private InputStream in;
    private OutputStream out;
    private boolean isDebugMode;
    private Timer timer = new Timer();

    private void run(InputStream in, OutputStream out, boolean isDebugMode) throws IOException {
        this.in = in;
        this.out = out;
        this.isDebugMode = isDebugMode;

//        int t = in.nextInt();
//        for (int i = 0; i < t; i++) {
        solve();
//            out.flush();
//        }
    }

    private void solve() throws IOException {
        int n = in.nextInt();
        int m = in.nextInt();

        int[] primes = new int[32000];
        primes[0] = 2;
        primes[1] = 3;
        int pc = 2;
        for (int i = 5; i < 32000; i += 2) {
            boolean pp = true;
            for (int j = 0; j < pc && primes[j] * primes[j] <= i; j++) {
                if (i % primes[j] == 0) {
                    pp = false;
                    break;
                }
            }
            if (pp) {
                primes[pc] = i;
                pc++;
            }
        }


        int[] a = in.nextIntArray(n);
        int[] b = in.nextIntArray(m);
        HashSet<Integer> bb = new HashSet<Integer>();
        for (int i : b) bb.add(i);

        int c = 0;
        for (int i = 0; i < n; i++) {
            c += gc(primes, a[i], bb);
        }
        int ans = c;
        int gg = 1;
        for (int j = n - 1; j >= 0; j--) {
            int g = 0;
            for (int i = 0; i <= j; i++) {
                g = gcd(a[i] / gg, g);
            }
            int t = gc(primes, g, bb);
            if (t < 0) {
                gg *= g;
                ans -= gc(primes, g, bb) * (j+1);
            }
        }
        out.println(ans);
    }

    private int gc(int[] primes, int t, Set<Integer> bb) {
        int c = 0;
        for (int j = 0; primes[j] * primes[j] <= t; j++) {
            if (t % primes[j] == 0) {
                int p = primes[j];
                boolean pp = bb.contains(p);
                do {
                    if (pp) c--;
                    else c++;
                    t /= p;
                } while (t % p == 0);
            }
        }
        if (t > 1) {
            if (bb.contains(t)) c--;
            else c++;
        }
        return c;
    }

    private int gcd(int a, int b) {
        while (a > 0 && b > 0) {
            if (a > b) a %= b;
            else b %= a;
        }
        return a + b;
    }


// template beginning
// Author: Andrey Siunov
// Date: 29.08.2013

    private static class SegmentTree {
        public static interface MergeFunction {
            long calcValue(long first, long second);
        }

        private MergeFunction mergeFunction;
        private int n;
        private long[] values;

        public SegmentTree(ArrayList<Long> collection, MergeFunction mergeFunction) {
            this.mergeFunction = mergeFunction;
            n = collection.size();
            values = new long[n * 4];
            build(collection, 1, 0, n - 1);
        }

        private void build(ArrayList<Long> collection, int v, int tl, int tr) {
            if (tl == tr) {
                values[v] = collection.get(tl);
            } else {
                int tm = (tl + tr) >> 1;
                build(collection, v << 1, tl, tm);
                build(collection, (v << 1) + 1, tm + 1, tr);
                values[v] = mergeFunction.calcValue(values[v << 1], values[(v << 1) + 1]);
            }
        }

        public long getValue(int index) {
            return getValue(index, index);
        }

        public long getValue(int l, int r) {
            return getValue(1, 0, n - 1, l, r);
        }

        private Long getValue(int v, int tl, int tr, int l, int r) {
            if (l > r) {
                return null;
            }
            if (l == tl && r == tr) {
                return values[v];
            }
            int tm = (tl + tr) >> 1;
            Long leftValue = getValue(v << 1, tl, tm, l, Math.min(r, tm));
            Long rightValue = getValue((v << 1) + 1, tm + 1, tr, Math.max(l, tm + 1), r);
            return leftValue == null ? rightValue :
                    (rightValue == null ? leftValue : mergeFunction.calcValue(leftValue, rightValue));
        }
    }


    private static class Timer {
        private long lastTime = 0;

        private Timer() {
            lastTime = System.currentTimeMillis();
        }

        public void reset() {
            lastTime = System.currentTimeMillis();
        }

        public long getMillisAndReset() {
            long current = System.currentTimeMillis();
            long result = current - lastTime;
            lastTime = current;
            return result;
        }
    }

    private static class FileInputStream extends InputStream {
        private String inputFileName;

        public FileInputStream() throws IOException {
            this("input.txt");
        }

        public FileInputStream(String inputFileName) throws IOException {
            this.inputFileName = inputFileName;
        }

        @Override
        protected Reader getReader() throws IOException {
            return new FileReader(inputFileName);
        }
    }

    private static class ConsoleInputStream extends InputStream {
        @Override
        protected Reader getReader() throws IOException {
            return new InputStreamReader(System.in);
        }
    }

    private static abstract class InputStream {
        private static String DELIMITERS = " \t\n\r\f";
        private BufferedReader in;

        public InputStream open() throws IOException {
            in = new BufferedReader(getReader());
            return this;
        }

        private class Line {
            private Line(String inputLine) {
                this.inputLine = inputLine;
                stringTokenizer = new StringTokenizer(this.inputLine, DELIMITERS);
                readCharacters = 0;
            }

            private int readCharacters;
            private String inputLine = null;
            private StringTokenizer stringTokenizer = null;

            public String nextToken() {
                String result = stringTokenizer.nextToken();
                readCharacters += result.length();
                return result;
            }

            boolean hasNextToken() {
                return stringTokenizer.hasMoreTokens();
            }

            String getLineRest() {
                int position = 0;
                for (int remain = readCharacters; remain > 0; position++) {
                    if (DELIMITERS.indexOf(inputLine.charAt(position)) < 0) {
                        remain--;
                    }
                }
                return inputLine.substring(position);
            }
        }

        private Line currentLine = null;

        abstract protected Reader getReader() throws IOException;

        /**
         * Note: may be incorrect behavior if use this method with hasNextToken method
         */
        public String nextLine() throws IOException {
            setInputLine();
            if (currentLine == null) {
                return null;
            }
            String result = currentLine.getLineRest();
            currentLine = null;
            return result;
        }

        public boolean hasNextLine() throws IOException {
            setInputLine();
            return currentLine != null;
        }

        public String nextToken() throws IOException {
            return hasNextToken() ? currentLine.nextToken() : null;
        }

        /**
         * Note: may be incorrect behavior if use this method with nextLine method
         */
        public boolean hasNextToken() throws IOException {
            while (true) {
                setInputLine();
                if (currentLine == null || currentLine.hasNextToken()) {
                    break;
                } else {
                    currentLine = null;
                }
            }
            return currentLine != null;
        }

        public int nextInt() throws IOException {
            return new Integer(this.nextToken());
        }

        public long nextLong() throws IOException {
            return new Long(this.nextToken());
        }

        public double nextDouble() throws IOException {
            return new Double(this.nextToken());
        }

        public BigInteger nextBigInteger() throws IOException {
            return new BigInteger(this.nextToken());
        }


        public String[] nextTokensArray(int n) throws IOException {
            String[] result = new String[n];
            for (int i = 0; i < n; i++) {
                result[i] = this.nextToken();
            }
            return result;
        }

        public int[] nextIntArray(int n) throws IOException {
            int[] result = new int[n];
            for (int i = 0; i < n; i++) {
                result[i] = this.nextInt();
            }
            return result;
        }

        public long[] nextLongArray(int n) throws IOException {
            long[] result = new long[n];
            for (int i = 0; i < n; i++) {
                result[i] = this.nextLong();
            }
            return result;
        }

        public void close() throws IOException {
            currentLine = null;
            in.close();
        }

        private void setInputLine() throws IOException {
            if (currentLine == null) {
                String line = in.readLine();
                if (line != null) {
                    currentLine = new Line(line);
                }
            }
        }
    }

    private static class FileOutputStream extends OutputStream {
        private String outputFileName;

        public FileOutputStream() throws IOException {
            this("output.txt");
        }

        public FileOutputStream(String outputFileName) throws IOException {
            this.outputFileName = outputFileName;
        }

        @Override
        protected Writer getWriter() throws IOException {
            return new FileWriter(outputFileName);
        }
    }

    private static class ConsoleOutputStream extends OutputStream {
        @Override
        protected Writer getWriter() throws IOException {
            return new OutputStreamWriter(System.out);
        }
    }

    private static abstract class OutputStream {
        private PrintWriter out;

        public OutputStream open() throws IOException {
            out = new PrintWriter(getWriter());
            return this;
        }

        abstract protected Writer getWriter() throws IOException;

        public void print(Object... s) {
            for (Object token : s) {
                out.print(token);
            }
        }

        public void println(Object... s) {
            print(s);
            out.println();
        }

        public void println() {
            out.println();
        }

        public void flush() throws IOException {
            out.flush();
        }

        public void close() throws IOException {
            out.flush();
            out.close();
        }
    }


    private static class Pair<K, V> {
        private K key;
        private V value;

        Pair(K key, V value) {
            this.key = key;
            this.value = value;
        }

        K getKey() {
            return key;
        }

        V getValue() {
            return value;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Pair pair = (Pair) o;

            if (key != null ? !key.equals(pair.key) : pair.key != null) return false;
            if (value != null ? !value.equals(pair.value) : pair.value != null) return false;

            return true;
        }

        @Override
        public int hashCode() {
            int result = key != null ? key.hashCode() : 0;
            result = 31 * result + (value != null ? value.hashCode() : 0);
            return result;
        }

        @Override
        public String toString() {
            return "Pair{" +
                    "key=" + key +
                    ", value=" + value +
                    '}';
        }
    }
}
