Game With Numbers

Two players are playing a game. They are given an array $a_1, a_2, \dots, a_n$ and an array $b_1, b_2, \dots, b_m$.

The game consists of $m$ rounds. The players take turns alternately. In round $i$ (for $i$ from $1$ to $m$), the first player moves if $i$ is odd and the second player moves if $i$ is even. That player must do exactly one of the following:

• remove all elements from $a$ that are divisible by $b_i$,
• remove all elements from $a$ that are not divisible by $b_i$.

The first player wants to minimize the sum of the elements remaining in $a$ after all $m$ rounds, and the second player wants to maximize it. Find the sum of the remaining elements of $a$ after all $m$ rounds if both players play optimally.

The first line contains two integers $n$ and $m$ ($1 \le n \le 2 \cdot 10^4$, $1 \le m \le 2 \cdot 10^5$), the length of $a$ and the number of rounds.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($-4 \cdot 10^{14} \le a_i \le 4 \cdot 10^{14}$), the elements of $a$.

The third line contains $m$ integers $b_1, b_2, \dots, b_m$ ($1 \le b_i \le 4 \cdot 10^{14}$), the elements of $b$.

Print a single integer, the sum of the remaining elements of $a$ after all $m$ rounds if both players play optimally.

In the first sample, one possible course of the game is the following:

• Round 1: the first player removes all elements of $a$ divisible by $2$. $a$ becomes $(5, 7)$.
• Round 2: the second player removes all elements of $a$ divisible by $5$. $a$ becomes $(7)$. If the player had removed all elements not divisible by $5$, $a$ would become $(5)$, which has a smaller sum, and the second player does not want that.