Marginimas

Interview

Time limit1sMemory limit1024 MB

Summary

Count the eggs fully painted within N hours, where an egg is complete only if every robot works in the hour it is placed, so the answer is N divided by the LCM of all a_i.

Level: Easy3 of 10
Topics: Math, Number theory
Solved: No attempts yet

Statement

Easter is N hours away, and the Hare is behind on his work. He has R robots to paint the eggs and plans to hand the job over to them.

Each robot paints one ornament, and all the robots paint different ornaments. An egg counts as fully painted once every robot has painted its ornament on it.

The robots work in shifts. Robot $i$ paints an egg every $a_i$ hours: its first egg at hour $a_i$ , its second at hour $2a_i$ , and so on.

Every hour the Hare places one egg on the conveyor. Every robot working that hour paints its ornament on the egg on the conveyor.

The Hare and the robots work for N hours without a break, with hours numbered from 1 to N. The Hare has noticed that most eggs are not fully painted.

The Hare wants to know how many eggs the robots will fully paint by Easter. Write a program that counts the fully painted eggs after N hours.

Input

The first line contains two integers N and R.

The second line contains R integers $a_1, a_2, \ldots, a_R$ , separated by spaces.

Output

Print one integer: the number of fully painted eggs.

Constraints

$1 \le N \le 1\,000\,000$

$1 \le R \le 400\,000$

$1 \le a_i \le 100$ (for $1 \le i \le R$ )

The data guarantee that the robots fully paint at least one egg.

Examples1

Example 1
Input
```
10 2
2 4
```
Expected output
```
2
```