25779번 - Which Number 다국어

Natasha likes counting, but she has been told that a certain set of prime numbers are bad luck. Thus, she skips those numbers and all of their multiples entirely. For example, if 3, 5 and 11 are the primes she is avoiding, then when she starts counting, she'll list the following integers:

1, 2, 4, 7, 8, 13, 14, 16, 17, 19, 23, …

You are curious, what is the n th number Natasha will say?

Given the prime numbers whose multiples Natasha avoids, determine the n th number she will say when she starts counting from 1.

The first input line contains two integers: n (1 ≤ n ≤ 10¹⁷), indicating the number for the query, and k (1 ≤ k ≤ 14), indicating the number of distinct prime numbers that Natasha avoids when counting (again, the multiples of these primes are avoided as well when counting). The second input line has k distinct prime numbers on it, representing the numbers (and multiples) which Natasha avoids. Assume that the product of all these primes will not exceed 10¹⁷, e.g., the list of prime numbers can be {2, 3, 5, 11} since their product (330) does not exceed 10¹⁷ but the list of prime numbers will not be {1000000007, 1000000009} since their product exceeds 10¹⁷. Note that, as illustrated in the Sample Input, the primes can be listed in any order (i.e., they are not necessarily listed in increasing order).

Print the n th number Natasha will say.