Integer Game

Time limit2sMemory limit512 MB

Summary

Given N and up to 15 divisors, remove multiples of each in order and count how many numbers from 1 to N survive.

Level: Medium6 of 10
Topics: Math, Number theory, Combinatorics, Bit manipulation
Solved: No attempts yet

Problem

Jaehyun plays an integer game with the following rules.

Fix an integer $N$ and an array $A$ of length $K$ .
Write every integer from $1$ to $N$ on a sheet of paper.
Take the first number of $A$ and remove it from the array. Calling that number $x$ , erase every multiple of $x$ written on the paper.
Repeat step 3 until the array is empty.

Write a program that counts how many numbers are still written on the paper after the game ends.

Input

The first line contains $N$ and $K$ . ( $1 \le N \le 10^9$ , $1 \le K \le 15$ )

The second line contains the $K$ elements of $A$ in order. Each element is a natural number at most $100$ , and the same number may appear more than once.

Output

Print on the first line how many numbers are still written on the paper after the game ends.

Hint

If $N$ is $10$ and the array is $[2, 4, 5]$ , you erase the multiples of $2$ , then of $4$ , then of $5$ , and the paper keeps $1$ , $3$ , $7$ and $9$ .

Examples3

Example 1
Input
```
10 3
2 4 5
```
Expected output
```
4
```
Example 2
Input
```
60 4
2 3 4 6
```
Expected output
```
20
```
Example 3
Input
```
1 1
2
```
Expected output
```
1
```