Upgrading Array

题意翻译

给一个有n个数 a[1],a[2],…,a[n] 的数列打分,你认为 b[1],b[2]…,b[m] 是不好的质数。定义这个序列的分值为各个数的分值之和,设 x 的分值为 f(x),f(x)=f(x/p)+k (p 为 x 的最小质因子;若 p 为不好的质数, k 取 −1 ,否则 k 取 +1 ; f(1)=0 )。 你想让序列的分值更大,可以反复进行一项操作:$a[1],a[2],a[3],...,a[i](i<=n)$ 的每个数除以它们的最大公约数。请问你能让序列的得分最大为多少。 ## 输入格式: 首行两个整数$n,m(1<=n,m<=5000)$,下一行有$n$个数 $a[1],a[2],…,a[n]$,再下一行有$m$个数$b[1],b[2]…,b[m]$ 即为坏质数。(保证所有数不超过$10^9$, $b$ 数列都为质数且单调递增) ## 输出格式: 一个数 $s$ ,就是你能让序列得分的最大值。

题目描述

You have an array of positive integers $ a[1],a[2],...,a[n] $ and a set of bad prime numbers $ b_{1},b_{2},...,b_{m} $ . The prime numbers that do not occur in the set $ b $ are considered good. The beauty of array $ a $ is the sum ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF402D/aea4eb2d17c24d3a2d1067454589473b9ea01095.png), 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 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF402D/8afcd99c67c49a2d759fe9b7228c1f8d0e576b6a.png), otherwise ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF402D/cce5ab868ac31145b115c9c6f231d8d473326030.png). 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: ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF402D/7da2ca9ebcb0c358dd26347b51043ad8cf29f6d1.png), ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF402D/41a62953f2b193f6f57ad5e6aa04be0947094a88.png), $ ... $ , ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF402D/7947630aa7cab27f0ca3ac2ef6955b60eb99bea8.png). What is the maximum beauty of the array you can get?

输入输出格式

输入格式


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]<=10^{9} $ ) — array $ a $ . The third line contains $ m $ space-separated integers $ b_{1},b_{2},...,b_{m} $ ( $ 2<=b_{1}&lt;b_{2}&lt;...&lt;b_{m}<=10^{9} $ ) — the set of bad prime numbers.

输出格式


Print a single integer — the answer to the problem.

输入输出样例

输入样例 #1

5 2
4 20 34 10 10
2 5

输出样例 #1

-2

输入样例 #2

4 5
2 4 8 16
3 5 7 11 17

输出样例 #2

10

说明

Note that the answer to the problem can be negative. The GCD( $ x_{1} $ , $ x_{2} $ , ..., $ x_{k} $ ) is the maximum positive integer that divides each $ x_{i} $ .