有两个玩家在玩一个游戏。他们拥有一个数组 $a_1, a_2, \dots, a_n$ 以及一个数组 $b_1, b_2, \dots, b_m$。

游戏包含 $m$ 轮。玩家轮流参与每一轮。在第 $i$ 轮（$i$ 从 $1$ 到 $m$），对应的玩家（如果 $i$ 为奇数则为先手，如果 $i$ 为偶数则为后手）必须执行以下操作之一：

• 从数组 $a$ 中移除所有能被 $b_i$ 整除的元素。
• 从数组 $a$ 中移除所有不能被 $b_i$ 整除的元素。

先手希望在 $m$ 轮结束后最小化数组 $a$ 中剩余元素的总和，而后手希望最大化该总和。如果双方都采取最优策略，求 $m$ 轮结束后数组 $a$ 中剩余元素的总和。

输入格式

第一行包含两个整数 $n, m$ ($1 \le n \le 2 \cdot 10^4, 1 \le m \le 2 \cdot 10^5$)，分别表示数组 $a$ 的长度和游戏的轮数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($-4 \cdot 10^{14} \le a_i \le 4 \cdot 10^{14}$)，表示数组 $a$ 的元素。

第三行包含 $m$ 个整数 $b_1, b_2, \dots, b_m$ ($1 \le b_i \le 4 \cdot 10^{14}$)，表示数组 $b$ 的元素。

输出格式

输出一个整数，表示双方采取最优策略时，游戏结束后数组 $a$ 中剩余元素的总和。

样例

样例输入 1

6 2
2 2 5 2 2 7
2 5

样例输出 1

7

样例输入 2

5 1
-5000111000 -5000222000 -15 5 2
5

样例输出 2

-10000333010

说明

在第一个样例中，一种可能的游戏过程如下：

• 第 1 轮：先手从 $a$ 中移除所有能被 $2$ 整除的元素，$a$ 变为 $(5, 7)$。
• 第 2 轮：后手从 $a$ 中移除所有能被 $5$ 整除的元素，$a$ 变为 $(7)$。如果他移除的是所有不能被 $5$ 整除的元素，$a$ 将变为 $(5)$，其元素之和更小，因此这对后手而言不是最优选择。

子任务

1. (3 分): $m = 1$
2. (6 分): $b_{i+1} = b_i$ ($1 \le i < m$)，即数组 $b$ 的所有元素相同
3. (15 分): $b_{i+1} \pmod{b_i} = 0$ ($1 \le i < m$)
4. (9 分): $1 \le m \le 7$
5. (11 分): $1 \le m \le 20$
6. (15 分): $1 \le m \le 100$
7. (18 分): $1 \le a_i, b_i \le 10^9$
8. (11 分): $m \pmod 2 = 0, b_{2i-1} = b_{2i}$ ($1 \le i \le \frac{m}{2}$)
9. (12 分): 无附加限制