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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.UncheckedIOException;
import java.io.Closeable;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.lang.reflect.Array;
import java.util.Arrays;


public class water {
    public static int gys(int x,int y){
        for(;x!=0&&y!=0;){
            if(x>y){
                x=x%y;
            }
            else {
                y=y%x;
            }
        }
        if(y==0)
        return x;
        else return y;
    }
    public static int [][] fj(int x){
        int a[][];
        int poi=0,test=x;
        for(int i=0;sus[i]<=test&&i<len;i++){
                if(test%sus[i]==0){
                    for(;test%sus[i]==0;){
                        poi++;
                        test/=sus[i];
                    }
                }
        }
        if(test!=1)
            poi++;
        a=new int [poi][2];
        poi=0;
        test=x;
        for(int i=0;sus[i]<=test&&i<len;i++){
            if(test%sus[i]==0){
                a[poi][0]=sus[i];
                for(;test%sus[i]==0;){
                    a[poi][1]++;
                    test=test/sus[i];
                }
                poi++;
            }
        }
        if(test!=1){
            a[poi][0]=test;
            a[poi][1]=1;
        }

        return a;
    }
    public static int  fj1(int x,int b[]){
        int a=0;
        int poi=0,test=x;
        for(int i=0;sus[i]<=test&&i<len;i++){
          if(test%sus[i]==0){
                if(Arrays.binarySearch(b,sus[i])<0){
                    for(;test%sus[i]==0;){
                        a++;
                        test=test/sus[i];
                    }
                }
                else {
                    for(;test%sus[i]==0;){
                        a--;
                        test=test/sus[i];
                    }
                }
            }
        }
        if(test!=1){
            if(Arrays.binarySearch(b,test)<0)
                return a+1;
            else
                return a-1;
        }
        return a;
    }
    public static int sus[]=new int [100000];
    public static int len=4,inf=10;
    public static boolean sushu(int x){
        for(;inf<=x;inf+=10){
            boolean is;
            is=false;
            for(int j=0;j<len&&sus[j]<(Math.sqrt(inf+1)+1);j++){
                if((inf+1)%sus[j]==0) is=true;
            }
            if(!is){
                sus[len++]=inf+1;
            }
            is=false;
            for(int j=0;j<len&&sus[j]<(Math.sqrt(inf+3)+1);j++){
                if((inf+3)%sus[j]==0) is=true;
            }
            if(!is){
                sus[len++]=inf+3;
            }
            is=false;
            for(int j=0;j<len&&sus[j]<(Math.sqrt(inf+7)+1);j++){
                if((inf+7)%sus[j]==0) is=true;
            }
            if(!is){
                sus[len++]=inf+7;
            }
            is=false;
            for(int j=0;j<len&&sus[j]<(Math.sqrt(inf+9)+1);j++){
                if((inf+9)%sus[j]==0) is=true;
            }
            if(!is){
                sus[len++]=inf+9;
            }
        }
        return true;
    }
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastInput input = new FastInput(inputStream);
        FastOutput out = new FastOutput(outputStream);
        sus[0]=2;
        sus[1]=3;
        sus[2]=5;
        sus[3]=7;
        int n= input.scanInt();
        int m= input.scanInt();
        int a[]=new int [n];
        int b[]=new int [m];
        for(int i=0;i<n;i++){
            a[i]= input.scanInt();
        }
        for(int i=0;i<m;i++){
            b[i]= input.scanInt();
        }
        int c[]=new int [n];
        c[0]=a[0];
        for(int i=1;i<n;i++){
            c[i]=gys(c[i-1],a[i]);
        }

        int sum=0;
        sushu(100000);
        int add=0;
        for(int i=n-1;i>=0;i--){
            int d[][];
            if(add==0)
                d=fj(c[i]);
            else{
                d=fj(c[i]/c[i+1]);
            }
                for(int j=0;j<d.length;j++){
                    if(Arrays.binarySearch(b,d[j][0])<0){
                        add-=d[j][1];
                    }
                    else{
                        add+=d[j][1];
                    }
                }
                if(add>0){
                    int pox=c[i];
                    for(int j=0;j<=i;j++){
                        a[j]/=pox;
                        c[j]/=pox;
                    }
                    add=0;
                }
        }


        for(int i=0;i<n;i++){
            sum+=fj1(a[i],b);
        }
        System.out.println(" "+ sum);
    }

    static class FastInput {
        private final InputStream is;
        private StringBuilder defaultStringBuf = new StringBuilder(1 << 13);
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;
        public FastInput(InputStream is) {
            this.is = is;
        }
        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    bufLen = -1;
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }
        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }
        public String next() {
            return readString();
        }
        public int scanInt() {
            int sign = 1;
            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }
            int val = 0;
            while (next >= '0' && next <= '9') {
                val = val * 10 + next - '0';
                next = read();
            }
            return (sign*val);
        }

        public String readString(StringBuilder builder) {
            skipBlank();
            while (next > 32) {
                builder.append((char) next);
                next = read();
            }
            return builder.toString();
        }

        public String readString() {
            defaultStringBuf.setLength(0);
            return readString(defaultStringBuf);
        }

    }
    static class FastOutput implements AutoCloseable, Closeable, Appendable {
        private StringBuilder cache = new StringBuilder(1 << 20);
        private final Writer os;

        public FastOutput append(CharSequence csq) {
            cache.append(csq);
            return this;
        }

        public FastOutput append(CharSequence csq, int start, int end) {
            cache.append(csq, start, end);
            return this;
        }

        public FastOutput(Writer os) {
            this.os = os;
        }

        public FastOutput(OutputStream os) {
            this(new OutputStreamWriter(os));
        }

        public FastOutput append(char c) {
            cache.append(c);
            return this;
        }

        public FastOutput append(String c) {
            cache.append(c);
            return this;
        }
        public FastOutput append(int c) {
            cache.append(c);
            return this;
        }
        public FastOutput println(int c) {
            return append(c).println();
        }
        public FastOutput println(String c) {
            return append(c).println();
        }

        public FastOutput println() {
            //cache.append(System.lineSeparator());
//            flush();
            return this;
        }

        public FastOutput flush() {
            try {
                os.append(cache);
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
            return this;
        }

        public void close() {
            flush();
            try {
                os.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        public String toString() {
            return cache.toString();
        }

    }


}




