2014 Mock CCC by Alex and Timothy

Alice had recently pursued her (not so) secret love interest, Bob, on a long roadtrip to see just who he was meeting in another town. To her dismay, she learned that Bob was getting back together with one of his ex-girlfriends. As she made the discovery, her body convulsed with rage, the sky spun around her head, and the ground trembled under her feet. One thing led to another; before you know it, Bob has found himself tied up and gagged in Alice's basement. Because Bob is a computer scientist, Alice stands before him offering him only two options — play the Elimination Game with her, or prepare to be eliminated. If she can't have him, nobody can!

To play the Elimination Game, Alice presents Bob with two piles of cards — a pile of ~N~ black cards and a pile of ~M~ white cards ~(1 \le N, M \le 100)~. Every card has a positive integer no greater than ~100\,000~ written on it. The rules of the game are as follows:

• Bob picks two cards — one from the black pile and one from the white pile, such that the numbers on both cards share a factor greater than ~1~.
• The two cards are eliminated from their respective piles.
• Bob repeats this process until there are no more pairs that can be eliminated.
• The objective is to eliminate as many cards as possible.

Using many days and nights of computational power from a supercomputer, Alice has obtained the maximum (total) number of cards that can be eliminated from the two piles under these rules. If Bob finds this number, then he is free to go. Otherwise, he himself will be forever "eliminated" by the crazed, lust-driven Alice. Write a program that helps Bob escape!

Scoring

Bob immediately comes up with a strategy. He decides to start at the beginning of the black cards and go through them one by one. For each card in the black pile, he goes through all of the (non-eliminated) cards in the white pile from beginning to end. If at any one point the two cards he's examining can be eliminated, he eliminates them and moves on to the next black card. If no white cards share a factor greater than ~1~ with the black card, he then skips to the next black card. Clearly, this strategy is not perfect and will not always lead to the correct answer. However, implementing it efficiently will get you at least ~5/15~ of the points.

On an unrelated note:

• For test cases worth ~5/15~ of the points: ~N~, ~M \le 5~.
• For test cases worth ~10/15~ of the points: ~N~, ~M \le 10~.

Input Specification

Line ~1~ of input contains the two integers ~N~ and ~M~.
Line ~2~ contains ~N~ integers, the values of the black cards.
Line ~3~ contains ~M~ integers, the values of the white cards.

Output Specification

The output should contain one integer, the maximum total number of cards that can be eliminated from the piles.

Sample Input

5 5
3 10 6 7 17
3 5 14 4 15

Sample Output

8

Explanation

One way to eliminate ~8~ of the ~10~ cards is to eliminate the pairs ~(3, 3)~, ~(10, 5)~, ~(6, 4)~, and ~(7, 14)~, with ~17~ left over in the black pile and ~15~ left over in the white pile. Another way is to eliminate the pairs ~(3, 15)~, ~(10, 5)~, ~(6, 3)~, and ~(7, 14)~, with ~17~ left over from the black pile and ~4~ left over from the white pile. We know that it's not possible to eliminate all ~10~ cards because we cannot eliminate ~17~, since it does not share factors greater than ~1~ with any other number except for itself (and there are no ~17~'s in the white pile). Therefore, ~8~ is the most we can eliminate.