URI Online Judge | 2524

Strawberry Candies

By Ricardo Oliveira, UFPR BR Brazil

Timelimit: 1

Madam Beauvoir’s N grandchildren are really prankish, but they are also really nice sometimes. One day, they made a big mess with the doors of her mansion! The following day, however, they behaved really nice. Due to this, madam Beauvoir decided to reward her grandchildren with strawberry candies.

Right now, she is at the candy shop to buy the candies. The total number of candies she buys must be such that (i) all candies must be given to her grandchildren; and (ii) every grandchild must receive the same number of candies. Please notice that the number of candies each child receives is irrelevant, provided that everyone receives the same number of candies.

There are M candies packages in the shop. Package i (1 ≤ iM) contains Bi strawberry candies. The seller can only sell entire packages, i.e., madam Beauvoir cannot open a package and buy some (not all) candies from inside it.

Since she is really rich, she does not care about the price of each package. In fact, to impress the kids, she wants to buy the maximum possible number of packages. Your task is to determine what is the maximum possible number of packages she can buy such that the total number of candies can be divided by her grandchildren.


The input contains several test cases. The first line of each test case contains two integers N and M (1 ≤ N, M ≤ 103). The second line contains M integers Bi (1 ≤ Bi ≤ 109), indicating the number of candies inside each package.

The input ends with end-of-file (EOF).


For each test case, print single a line containing the maximum possible number of packages she can buy.

Input Sample Output Sample

10 3
3 4 7
10 4
12 7 2 6