P13784 [eJOI 2022] Game With Numbers

Two players are playing a game. They are given an array $a_1, a_2, \ldots, a_n$ as well as an array $b_1, b_2, \ldots, b_m$. The game consists of $m$ rounds. Players are participating in rounds alternatively. During the $i$-th round (for $i$ from 1 to $m$) the corresponding player (first player, if $i$ is odd, and second if $i$ is even) has to do exactly one of the following: - remove all elements from the array $a$ that are divisible by $b_i$, - remove all elements from the array $a$ that are not divisible by $b_i$. The first player wants to minimize the sum of the remaining elements in the array $a$ after all $m$ rounds, and the second wants to maximize it. Find the sum of the remaining elements in the array $a$ after all $m$ rounds if both players are playing optimally.

The first line contains two integers $n, m$ ($1 \leq n \leq 2 \cdot 10^4$, $1 \leq m \leq 2 \cdot 10^5$) - the length of the array $a$ and the number of rounds in the game. The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-4 \cdot 10^{14} \leq a_i \leq 4 \cdot 10^{14}$) - the elements of the array $a$. The third line contains $m$ integers $b_1, b_2, \ldots, b_m$ ($1 \leq b_i \leq 4 \cdot 10^{14}$) - the elements of the array $b$.

Output a single integer - the sum of the remaining elements of the array $a$ after all $m$ rounds if both players are playing optimally.

### Note In the first sample, one possible flow of the game is the following: - Round 1: first player removes from $a$ all elements divisible by $2$. $a$ becomes $(5, 7)$. - Round 2: second player removes from $a$ all elements divisible by $5$. $a$ becomes $(7)$. If he had removed from $a$ all elements not divisible by $5$, $a$ would become $(5)$, which has a smaller sum of elements and therefore is not desirable for the second player. ### Scoring 1. (3 points): $m = 1$ 2. (6 points): $b_{i+1} = b_i$ ($1 \leq i < m$), i.e. all elements of the array $b$ are the same 3. (15 points): $b_{i+1} \mod b_i = 0$ ($1 \leq i < m$) 4. (9 points): $1 \leq m \leq 7$ 5. (11 points): $1 \leq m \leq 20$ 6. (15 points): $1 \leq m \leq 100$ 7. (18 points): $1 \leq a_i, b_i \leq 10^9$ 8. (11 points): $m \bmod 2 = 0$, $b_{2i-1} = b_{2i}$ ($1 \leq i \leq \frac{m}{2}$) 9. (12 points): No additional constraints