题目描述

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.

6 2
2 2 5 2 2 7
2 5

7

5 1
-5000111000 -5000222000 -15 5 2
5

-10000333010

提示

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