#213883. [eJOI 2022] Game With Numbers

Two players are playing a game. They are given an array as well as an array .

The game consists of rounds. Players are participating in rounds alternatively. During the -th round (for from 1 to ) the corresponding player (first player, if is odd, and second if is even) has to do exactly one of the following:

• remove all elements from the array that are divisible by ,
• remove all elements from the array that are not divisible by .

The first player wants to minimize the sum of the remaining elements in the array after all rounds, and the second wants to maximize it. Find the sum of the remaining elements in the array after all rounds if both players are playing optimally.

The first line contains two integers (, ) - the length of the array and the number of rounds in the game.

The second line contains integers () - the elements of the array .

The third line contains integers () - the elements of the array .

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

样例输入 1

6 2
2 2 5 2 2 7
2 5

样例输出 1

7

样例输入 2

5 1
-5000111000 -5000222000 -15 5 2
5

样例输出 2

-10000333010

Note

In the first sample, one possible flow of the game is the following:

• Round 1: first player removes from all elements divisible by . becomes .
• Round 2: second player removes from all elements divisible by . becomes . If he had removed from all elements not divisible by , would become , which has a smaller sum of elements and therefore is not desirable for the second player.

Scoring

1. (3 points):
2. (6 points): (), i.e. all elements of the array are the same
3. (15 points): ()
4. (9 points):
5. (11 points):
6. (15 points):
7. (18 points):
8. (11 points): , ()
9. (12 points): No additional constraints