MOMOS - FEASTOFPIGS


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 jthpig 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.

You're 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 ith pig(i.e. a[i]).

It is guaranteed that:

 

Either (1 ≤ N ≤ 106 and 1 ≤ K ≤ 100) or (1≤ N ≤ 1014 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

 

 

 

 


hide comments
nadstratosfer: 2021-06-15 00:36:46

Good idea having 2 kinds of testfiles, however TL is probably unbeatable for slower languages; my PyPy solution needs about 1.55s for a worst-case file.

Pythonists should try NGM2 instead.

Edit 2021-08-08: Thanks for adjusting the TL, PyPy can pass now.

Last edit: 2021-08-08 00:22:51

Added by:Salil
Date:2020-04-13
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Inspired from IARCS judge problems