Cải thiện mảng

Cho một mảng gồm $n$ số nguyên dương $a_1,a_2,\dots ,a_n$ và một tập hợp gồm $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.

Định nghĩa hàm $f(s)$ như sau:

• $f(1)=0$;
• Với $s>1$, phân tích $s$ thành thừa số nguyên tố. Khi đó $f(s)$ bằng (số thừa số nguyên tố tốt, tính cả bội) trừ đi (số thừa số nguyên tố xấu, tính cả bội).

Nói cách khác, mỗi lần một số nguyên tố tốt xuất hiện trong phân tích của $s$ thì cộng $1$, mỗi lần một số nguyên tố xấu xuất hiện thì trừ $1$.

Độ đẹp của mảng $a$ là tổng $f(a_1)+f(a_2)+\cdots +f(a_n)$.

Bạn được phép thực hiện một số lần tùy ý (có thể bằng $0$) thao tác sau để cải thiện mảng:

• Chọn một chỉ số $r$ ($1\le r\le n$), tính $g=gcd(a_1,a_2,\dots ,a_r)$.
• Thay mỗi $a_i$ (với $1\le i\le r$) bằng $a_i/g$.

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

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$.
• 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<\cdots <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, độ đẹp lớn nhất đạt được.

Ràng buộc

• $1\le n,m\le 5000$
• $1\le a_i\le {10}^9$
• $2\le b_1<b_2<\cdots <b_m\le {10}^9$, tất cả $b_i$ đều là số nguyên tố.

Ví dụ