题目描述

两名玩家正在玩一个游戏。给定一个数组 $a_1, a_2, \ldots, a_n$，以及一个数组 $b_1, b_2, \ldots, b_m$。

游戏共有 $m$ 轮，两名玩家轮流进行操作。在第 $i$ 轮（$1 \leq i \leq m$）中，当前轮到的玩家（若 $i$ 为奇数则是第一名玩家，若 $i$ 为偶数则是第二名玩家）必须执行以下两种操作之一：

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

第一名玩家的目标是最小化在 $m$ 轮结束后数组 $a$ 中剩余元素的和，而第二名玩家的目标是最大化这个和。若两名玩家都采取最优策略，请求出 $m$ 轮结束后数组 $a$ 中剩余元素的和。

输入格式

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

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

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

输出格式

输出一个整数，表示在两名玩家都采取最优策略的情况下，$m$ 轮操作结束后数组 $a$ 中剩余元素的和。

6 2
2 2 5 2 2 7
2 5

7

5 1
-5000111000 -5000222000 -15 5 2
5

-10000333010

提示

样例解释

在第一个样例中，游戏可能的最优流程如下：

• 第 1 轮：第一名玩家移除所有能被 $2$ 整除的元素，$a$ 变为 $(5, 7)$。
• 第 2 轮：第二名玩家移除所有能被 $5$ 整除的元素，$a$ 变为 $(7)$。
  如果他选择移除不能被 $5$ 整除的元素，则 $a$ 会变为 $(5)$，其元素和更小，这对第二名玩家来说不是最优选择。

评分规则

1. （3 分）：$m = 1$
2. （6 分）：$b_{i+1} = b_i$（$1 \leq i < m$），即数组 $b$ 中所有元素相同
3. （15 分）：$b_{i+1} \bmod b_i = 0$（$1 \leq i < m$）
4. （9 分）：$1 \leq m \leq 7$
5. （11 分）：$1 \leq m \leq 20$
6. （15 分）：$1 \leq m \leq 100$
7. （18 分）：$1 \leq a_i, b_i \leq 10^9$
8. （11 分）：$m \bmod 2 = 0$ 且 $b_{2i-1} = b_{2i}$（$1 \leq i \leq \frac{m}{2}$）
9. （12 分）：无额外限制

翻译由 ChatGPT-5 完成