题目描述

$\text{Alice}$ 和 $\text{Bob}$ 又在一起在玩游戏，这次游戏的规则是：

$1$. $\text{Alice}$ 先手， $\text{Bob}$ 后手，轮流进行操作，共有 $m$ 轮操作，有一个集合初始为 $S=\{a_1,a_2,...,a_n\}$。

$2$. 第 $i$ 轮操作有一个参数 $b_i$，当前轮的操作者有以下两个选择：保留 $S$ 中所有是 $b_i$ 倍数的数字，或者保留 $S$ 中所有不是 $b_i$ 倍数的数字。

$3$. 进行了 $m$ 轮操作后两人获得的权值是 $S$ 中的数字之和，$S$ 可以为空。

$\text{Alice}$ 希望权值最小， $\text{Bob}$ 希望权值最大，假设他们都足够聪明，那么游戏最终的权值是多少。

输入格式

第一行两个整数 $n,m$，表示集合大小和操作轮数。

第二行 $n$ 个整数 $a_i$，表示初始集合。

第三行 $m$ 个整数 $b_i$，为第 $i$ 轮的参数。

输出格式

输出一个数表示博弈的结果。

10 3
13 -6 -9 -8 11 5 -4 -9 -4  -7
2 3 3

-6

数据规模与约定

对于 $100\%$ 的数据，$1≤n≤2×10^4, 1≤m≤2×10^5, -4×10^{14}≤a_i≤4×10 ^{14},$ $1≤b_i≤4×10^{14}$。

大样例

大样例下载