시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 28 11 9 69.231%

문제

민호는 K개의 카드를 가지고 있는데 각각의 카드에는 양의 정수가 적혀 있다. 이 카드들을 너무 좋아하는 민호는 이것들을 이용해 재미있는 놀이를 생각해 냈다.

1이상 N이하의 양의 정수 중에서 민호가 가지고 있는 카드들 중 적어도 한개로 나눠떨어지는 숫자는 몇개인지 알아보는 것이다.

하지만 경우의 수가 너무 많아 손으로 셀 수 없다는 것을 깨달은 민호는 여러분들에게 도움을 요청했다. 민호를 도와 민호가 놀이를 성공적으로 마칠 수 있게 해주자.

입력

첫 번째 줄에 N, K ( 1 ≤ N ≤ 109 1 ≤ K ≤ 20 ) 이 공백을 구분으로 주어진다.

다음 줄에는 민호가 가지고 있는 K개의 카드에 적힌 숫자가 Ai (1 ≤ i ≤ N, 1 ≤ Ai ≤ 109)가 공백을 구분으로 차례대로 주어진다.

출력

1이상 N이하의 양의 정수 중 민호가 가지고 있는 카드들 중 적어도 한 개로 나눠떨어지는 수의 개수를 출력한다.

예제 입력 1

100 2
2 3

예제 출력 1

67

예제 입력 2

100 3
2 3 7

예제 출력 2

72