Lostborn

Igor K.은 멀티플레이어 롤플레잉 게임 WineAge II.을 매우 좋아한다. 어쩌면 그것이 그가 대학에서 좋은 성적을 내지 못하는 이유일지도 모른다. 이 게임을 하는 여느 사람과 마찬가지로, 그는 자신의 영웅에게 가능한 한 좋은 무기와 장비를 갖추어 주는 데 관심이 있다.

어느 날, 그는 또다시 게임 포럼을 읽다가 매우 흥미로운 사실을 발견했다. 알고 보니 게임의 각 무기는 k개의 서로 다른 수 a1, ..., ak로 특징지어진다. 이 수들을 타격 지표라고 하며, 게임 개발자들의 계획에 따르면 이들은 서로소이다.

타격 시 가해지는 피해량은 무기의 특성뿐만 아니라 영웅의 힘 수치에도 좌우된다. 따라서 영웅의 힘이 n와 같다면, 가해지는 피해량은 구간 에 있는 수들 가운데 어떤 타격 지표 ai로도 나누어떨어지지 않는 수의 개수로 계산된다.

최근 또 하나의 퀘스트를 완료한 Igor K.은 새로운 Lostborn 검을 발견했다. 그는 이 검을 사용하면 적들에게 얼마나 많은 피해를 줄지 알고 싶어 한다.

첫 번째 줄에는 두 정수 n와 k (1 ≤ n ≤ 1013, 1 ≤ k ≤ 100)가 주어진다. 이들은 Igor K's 영웅의 힘을 나타내는 지표와 타격 지표의 개수이다.

다음 줄에는 공백으로 구분된 k개의 정수 ai (1 ≤ ai ≤ 1000)가 주어진다. 이들은 Lostborn 검의 타격 지표이다. 주어진 k개의 수는 서로소이다.

Igor K.의 영웅이 새 무기를 사용할 때 가하게 될 피해량을 나타내는 하나의 수를 출력한다.

C++에서 64비트 정수를 읽거나 쓸 때 %lld 지정자를 사용하지 말라. cin, cout 스트림 또는 %I64d 지정자를 사용하는 것이 좋다.