Yet Another Contest 2 P3 - Maximum Damage

View as PDF

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 512M

Author:
Problem types

Mike is playing a strange video game!

There are enemies that Mike is able to attack. The -th enemy initially has an HP of .

In one attack, Mike can select a subset of the enemies containing at least enemies, and a positive integer such that . He must choose the subset and the value of such that is a factor of the HPs of all enemies in the subset. Then, the HPs of all enemies in the subset will be divided by .

Mike wants to attack the enemies as many times as possible. Can you help Mike find the maximum number of times he can perform an attack?

Input Specification

The first line contains a two space separated integer containing the values of and .

The next line contains space separated integers, , representing the initial HPs of the enemies.

Output Specification

On a single line, print the maximum possible number of attacks which can be performed.

Sample Input

3 2
5 12 10

Sample Output

2

Explanation

For the first attack, Mike can choose the first and third enemies in his subset, and choose . The HP of the first enemy is reduced to , and the HP of the third enemy is reduced to .

For the second attack, Mike can choose the second and third enemies in his subset, and choose . The HP of the second enemy is reduced to , and the HP of the third enemy is reduced to .

At this point, Mike cannot perform any more attacks. It can be shown that is the maximum possible number of attacks which Mike can perform.