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.