Nâng cấp mảng

Cho mảng $n$ số nguyên dương $a_1,a_2,\dots ,a_n$ và tập $m$ số nguyên tố xấu $b_1,b_2,\dots ,b_m$. Mọi số nguyên tố không nằm trong tập này được gọi là tốt.

Độ đẹp của mảng $a$ là tổng ${\sum }_{i=1}^{n}f(a_i)$, trong đó hàm $f$ được định nghĩa đệ quy như sau:

• $f(1)=0$;
• Gọi $p$ là ước nguyên tố nhỏ nhất của $s$. Nếu $p$ là số nguyên tố tốt thì $f(s)=f(s/p)+1$, ngược lại $f(s)=f(s/p)-1$.

Bạn được phép thực hiện một số lượng tuỳ ý (có thể bằng $0$) thao tác cải thiện mảng. Mỗi thao tác gồm các bước:

• Chọn một chỉ số $r$ bất kỳ ($1\le r\le n$) và tính $g=gcd(a_1,a_2,\dots ,a_r)$;
• Gán lại $a_i\leftarrow a_i/g$ với mọi $1\le i\le r$.

Hãy tìm độ đẹp lớn nhất của mảng mà bạn có thể đạt được. Lưu ý rằng đáp án có thể là số âm.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$: số phần tử của mảng và số lượng số nguyên tố xấu.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.
• Dòng thứ ba chứa $m$ số nguyên $b_1,b_2,\dots ,b_m$: tập các số nguyên tố xấu.

Dữ liệu ra

In ra một số nguyên duy nhất là đáp án của bài toán.

Ràng buộc

• $1\le n,m\le 5000$
• $1\le a_i\le {10}^9$
• $2\le b_1<b_2<\dots <b_m\le {10}^9$, mọi $b_j$ đều là số nguyên tố

Ví dụ