Alice and Bob 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. Alice goes first. During the ~i~-th round (for ~i~ from ~1~ to ~m~) the corresponding player (Alice, if ~i~ is odd, and Bob 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~.

Alice wants to minimize the sum of the remaining elements in the array ~a~ after all ~m~ rounds, and Bob wants to maximize the sum of the remaining elements in the array ~a~. Find the sum of the remaining elements in the array ~a~ after all ~m~ rounds if both Alice and Bob are playing optimally.

Input Specification

The first line contains two integers ~n~, ~m~ (~1 \le n \le 2 \times 10^4~, ~1 \le m \le 2 \times 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 \times 10^{14} \le a_i \le 4 \times 10^{14}~), the elements of the array ~a~.

The third line contains ~m~ integers ~b_1 , b_2 , \dots , b_m~ (~1 \le b_i \le 4 \times 10^{14}~), the elements of the array ~b~.

Output Specification

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

Subtask	Points	Additional constraints
~1~	~3~	~m = 1~
~2~	~6~	All ~b_i~ are the same, i.e ~b_1 = b_i~ (~1 \le i \le m~).
~3~	~15~	~b_{i+1} \mod b_{i} = 0~ (~1 \le i < m~).
~4~	~9~	~1 \le m \le 7~
~5~	~11~	~1 \le m \le 20~
~6~	~15~	~1 \le m \le 100~
~7~	~18~	~1 \le a_i, b_i \le 10^9~
~8~	~11~	~m \mod 2 = 0~, ~b_{2*i-1} = b_{2*i}~ (~1 \le i \le \frac{m}{2}~)
~9~	~12~	No additional constraints

Sample Input 1

6 2
2 2 5 2 2 7
2 5

Sample Output 1

7

Explanation for Sample 1

One possible move of the game is the following:

• Round 1: Alice removes from ~a~ all elements divisible by ~2~. ~a~ becomes ~[5, 7]~.
• Round 2: Bob 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.

Sample Input 2

5 1
-5000111000 -5000222000 -15 5 2
5

Sample Output 2

-10000333010