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.

------ 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_{N}  - the elements of the array A.

The third line contains M integers B_{1}, B_{2}, \ldots, B_{M} - 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 ------ 

$1 ≤ N ≤ 2 \cdot 10^{4}$
$1 ≤ M ≤ 2 \cdot 10^{5}$
$-4 \cdot 10^{14} ≤ A_{i} ≤ 4 \cdot 10^{14}$
$1 ≤ B_{i} ≤ 4 \cdot 10^{14}$

------ subtasks ------ 

Subtask 1 (22 points): $B_{i + 1} \bmod B_{i} = 0$ ($1 ≤ i < M$)
Subtask 2 (24 points): $1 ≤ M ≤ 20$
Subtask 3 (28 points): $1 ≤ M ≤ 100$
Subtask 4 (26 points): No additional constraints

----- Sample Input 1 ------ 
6 2
2 2 5 2 2 7
2 5
----- Sample Output 1 ------ 
7
----- explanation 1 ------ 
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.

Source: codechef | Difficulty: VERY_HARD
Tags: Complete search

Greedy algorithms


Solutions:
def ans(a, b, i):
	if len(a) == 0:
		return 0
	x = [[], []]
	for j in a:
		if j % b[i] == 0:
			x[0].append(j)
		else:
			x[1].append(j)
	if i == len(b) - 1:
		if i % 2 == 0:
			return min(sum(x[0]), sum(x[1]))
		else:
			return max(sum(x[0]), sum(x[1]))
	if i % 2 == 0:
		return min(ans(x[0], b, i + 1), ans(x[1], b, i + 1))
	else:
		return max(ans(x[0], b, i + 1), ans(x[1], b, i + 1))
n = list(map(int, input().strip().split()))
a = list(map(int, input().strip().split()))
b = list(map(int, input().strip().split()))
if n[1] > 50:
	print(0)
else:
	print(ans(a, b, 0))


from functools import lru_cache
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
q = list(map(int, input().split()))
ans = sum(a)

@lru_cache(maxsize=None)
def f(i, arr):
	if i == m:
		return sum(arr)
	divisible = []
	not_divisible = []
	for x in arr:
		if x % q[i] == 0:
			divisible.append(x)
		else:
			not_divisible.append(x)
	divisible = tuple(divisible)
	not_divisible = tuple(not_divisible)
	if i % 2 == 0:
		return min(f(i + 1, divisible), f(i + 1, not_divisible))
	else:
		return max(f(i + 1, divisible), f(i + 1, not_divisible))
if m > 30:
	print(0)
else:
	print(f(0, tuple(a)))