Remove Numbers Codechef Solution

Problem

Two players are playing a game. They are given an array A_1, A_2, \ldots, A_NA1​,A2​,…,AN​ as well as an array B_1, B_2, \ldots, B_MB1​,B2​,…,BM​.

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_iBi​,
• remove all elements from the array $A$ that are not divisible by B_iBi​.

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.

Input Format

The first line contains two integers $N$, $M$ $-$ 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_NA1​,A2​,…,AN​ $-$ the elements of the array $A$.

The third line contains $M$ integers B_1, B_2, \ldots, B_MB1​,B2​,…,BM​ $-$ the elements of the array $B$.

Output Format

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

Constraints

Subtasks

Sample 1:

6 2
2 2 5 2 2 7
2 5

7

Explanation:

In the 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.