M = int(input()) N = int(input()) C = list(map(int, input().split())) # Sieve of Eratosthenes to find primes up to M def sieve(n): if n < 2: return [False] * (n + 1), [] is_prime = [True] * (n + 1) is_prime[0], is_prime[1] = False, False for i in range(2, int(n ** 0.5) + 1): if is_prime[i]: for j in range(i * i, n + 1, i): is_prime[j] = False primes = [i for i, prime in enumerate(is_prime) if prime] return is_prime, primes is_prime, primes_list = sieve(M) # DP to compute the maximum number of cups for each sum up to M max_num = [-1] * (M + 1) max_num[0] = 0 # Base case: 0 money buys 0 cups for x in range(M + 1): if max_num[x] == -1: continue for c in C: next_x = x + c if next_x > M: continue if max_num[next_x] < max_num[x] + 1: max_num[next_x] = max_num[x] + 1 # Calculate the sum of valid k_p values sum_k = 0 for p in primes_list: required = M - p if required >= 0 and max_num[required] > 0: sum_k += max_num[required] # Calculate the maximum x for the last non-reset purchase max_x = 0 for x in range(M + 1): r = M - x if r < 0: continue if r == 0 or not is_prime[r]: if max_num[x] != -1 and max_num[x] > max_x: max_x = max_num[x] print(sum_k + max_x)