题目描述

本题译自 eJOI2022 Problem D. Game With Numbers

两个玩家正在玩一个游戏。给定他们两个数组 $a_1,a_2,\ldots,a_n$ 和 $b_1,b_2,\ldots,b_m$。

游戏包含 $m$ 轮。玩家按轮交替操作。在第 $i$ 轮（$i$ 从 $1$ 到 $m$），玩家（如果 $i$ 是奇数，则为第一位玩家，如果是偶数，则为第二位玩家）需要进行如下操作中的恰好一个：

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

第一位玩家想要最小化 $m$ 次操作后 $a$ 中剩余元素的和，第二位玩家想要最大化 $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,\ldots,a_n\ (-4\cdot 10^{14}\le a_i\le 4\cdot 10^{14})$，表示数组 $a$ 中的元素。

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

输出格式

输出一个整数，表示如果双方均使用最优策略操作，$m$ 次操作后数组 $a$ 中剩余元素的和。

6 2
2 2 5 2 2 7
2 5

7

一个可能的游戏过程如下所示：

• 第一轮：第一位玩家移除 $a$ 中所有能被 $2$ 整除的元素。$a$ 变为 $(5,7)$。
• 第二轮：第二位玩家移除 $a$ 中所有能被 $5$ 整除的元素。$a$ 变为 $(7)$。如果他移除 $a$ 中所有不能被 $5$ 整除的元素，$a$ 就会变为 $(5)$，$a$ 数组剩余元素之和就会变小，这不是第二位玩家所期望的。

5 1
-5000111000 -5000222000 -15 5 2
5

-10000333010

评分

详细子任务附加限制及分值如下表所示。