The pig's are having a feast tonight!! There are N momos numbered from 0 to N - 1. They are all arranged in a row on a table. Also K pigs are attending the feast. The j^thpig has hunger a[j]. A pig with hunger a[j] only eats all momos with number i such that when i is divided by a[j], the remainder is 0. For example, if there are 20 momos and a pig has hunger 3, then the pig will eat momos at position 0, 3, 6, 9, 12, 15, 18. Once a momo at a particular position is eaten by one pig, it cannot be eaten by a different pig.

Your task is simple, given the number of momos, and hunger of K pigs, find the total number of momos left after the feast.

Input

The first line of the input contains two integers N and K, where N is the number of momos and K is the number of pigs. Lines 2, 3 ... K + 1 describe the hunger of K pigs. Line i + 1 (1 ≤ i ≤ K) contains a single integer representing the hunger of the i^th pig (i.e. a[i]).

It is guaranteed that: either (1 ≤ N ≤ 10⁶ and 1 ≤ K ≤ 100) or (1 ≤ N ≤ 10¹⁴ and 1 ≤ K ≤ 20)

The hunger of every pig lies between 1 and N.

Output

A line containing a single integer, which is the number of momos left on the table after all pigs have finished eating.

Example

Input:
20 3
3
6
5

Output:
11