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.IOException;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.ArrayList;
import java.io.PrintStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Random;
import java.math.BigInteger;
import java.util.HashSet;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author karan173
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastReader in = new FastReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskB solver = new TaskB();
        solver.solve(1, in, out);
        out.close();
    }
}

class TaskB
{
    int n, m, a[], b[];
    HashSet<Integer> bad = new HashSet<Integer> ();
    MathUtils mathUtils;
    public void solve(int testNumber, FastReader in, PrintWriter out)
    {
        int MAXN = (int) Math.sqrt (1e9 + 6);
        mathUtils = new MathUtils ();
        mathUtils.sieve (MAXN);
        n = in.ni ();
        m = in.ni ();
        a = in.iArr (n);
        b = in.iArr (m);
        for (int i = 0; i < b.length; i++)
        {
            bad.add (b[i]);
        }
        long ans = 0;
        int hcf[] = new int[n];
        for (int i = 0; i < n; i++)
        {
            int x = a[i];
            ans += getAns (x);
//            out.println (getAns (x));
            if (i == 0)
            {
                hcf[i] = a[i];
            }
            else
            {
                hcf[i] = MathUtils.gcd (Math.max (hcf[i - 1], a[i]), Math.min (hcf[i - 1], a[i]));
            }
        }
//        out.println (ans);
        int divide = 1;
        for (int i = n - 1; i >= 0; i--)
        {
            hcf[i] /= divide;
            long x = getAns (hcf[i]);
            if (x < 0)
            {
//                out.println (i + " " + x);
                ans -= x * (i + 1);
                divide *= hcf[i];
            }
        }
        out.println (ans);
    }
    //returns good - bad
    private int getAns(int x)
    {
        int goodcnt = 0;
        int badcnt = 0;
        for (int p : MathUtils.primes)
        {
            int cnt = 0;
            while (x % p == 0)
            {
                x /= p;
                cnt++;
            }
            if (cnt == 0)
            {
                continue;
            }
            if (bad.contains (p))
            {
                badcnt +=cnt;
            }
            else
            {
                goodcnt += cnt;
            }
            if (x == 1)
            {
                return goodcnt-badcnt;
            }
        }
        if (x == 1)
        {
            return goodcnt-badcnt;
        }
        if (bad.contains (x))
        {
            badcnt++;
        }
        else
        {
            goodcnt++;
        }
        return goodcnt - badcnt;
    }
}

class MathUtils
{
    public static int gcd(int big, int small) // O(log min(a, b))
    {
        if (small == 0)
            return big;
        return gcd(small, big % small); // big%small<=small
    }

    public static ArrayList<Integer> primes;
   public static boolean[] flags;
   public int MAXN = 202;
   public void sieve(int MAXN)
   {
       // note flags for even are not set
       this.MAXN = MAXN;
       primes = new ArrayList<Integer>();
       flags = new boolean[MAXN+1];
       Arrays.fill(flags, true);
       flags[1] = false;
       int primeCnt = 1; // 2 in
       int p, i;
       primes.add(2);
       for (p = 3; p * p <= MAXN; p += 2) // dont traverse even
       {
           if (flags[p]) // prime
           {
               primes.add(p);
               // flags for all before p*p have been set
               //
               for (i = p * p; i < MAXN; i += p + p)
               {
                   flags[i] = false;
               }
           }
       }
       // now we have written primes till sqrt(MAXN) so all non primes flags
       // have been set
       for (; p <= MAXN; p += 2)
       {
           if (flags[p]) // prime
           {
               primes.add(p);
           }
       }
   }
    
    
    // NCR DP
    // O(n*n) precomputation -> dp, no overflow
    
    
    /*factor sieve -> O(n/2) memory      */

    }

class FastReader
{

    public InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
    private SpaceCharFilter filter;

    public FastReader(InputStream stream)
    {
        this.stream = stream;
    }

    public int read()
    {
        if (numChars == -1)
        {
            throw new InputMismatchException ();
        }
        if (curChar >= numChars)
        {
            curChar = 0;
            try
            {
                numChars = stream.read (buf);
            } catch (IOException e)
            {
                throw new InputMismatchException ();
            }
            if (numChars <= 0)
            {
                return -1;
            }
        }
        return buf[curChar++];
    }

    public int ni()
    {
        int c = read ();
        while (isSpaceChar (c))
            c = read ();
        int sgn = 1;
        if (c == '-')
        {
            sgn = -1;
            c = read ();
        }
        int res = 0;
        do
        {
            if (c < '0' || c > '9')
            {
                throw new InputMismatchException ();
            }
            res *= 10;
            res += c - '0';
            c = read ();
        } while (!isSpaceChar (c));
        return res * sgn;
    }

    public boolean isSpaceChar(int c)
    {
        if (filter != null)
        {
            return filter.isSpaceChar (c);
        }
        return isWhitespace (c);
    }

    public static boolean isWhitespace(int c)
    {
        return c==' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    public int[] iArr(int n)
    {
        int a[] = new int[n];
        for (int i = 0; i < n; i++)
        {
            a[i] = ni ();
        }
        return a;
    }

    public interface SpaceCharFilter
    {
        public boolean isSpaceChar(int ch);
    }
}
