「eJOI2022」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 \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$ 中剩余元素的和。

样例 1

输入

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$ 数组剩余元素之和就会变小，这不是第二位玩家所期望的。

样例 2

输入

5 1
-5000111000 -5000222000 -15 5 2
5

输出

-10000333010

评分

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