27462번 - Game With Numbers 서브태스크다국어

Two players are playing a game. They are given an array $a_1 , a_2 , \dots , a_n$ as well as an array $b_1 , b_2 , \dots , 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 ≤ n ≤ 2 ⋅ 10^4$, $1 ≤ m ≤ 2 ⋅ 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 , \dots , a_n$ ($-4 ⋅ 10^{14} ≤ a_i ≤ 4 ⋅ 10^{14}$) - the elements of the array $a$.

The third line contains $m$ integers $b_1 , b_2 , \dots , b_m$ ($1 ≤ b_i ≤ 4 ⋅ 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.

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.