def PrimeList(N): P = [1] * (N + 1) P[0] = P[1] = 0 for i in range(2, N + 1): if P[i]: for j in range(i + i, N + 1, i): P[j] = 0 PL = [] for i in range(N + 1): if P[i] == 1: PL.append(i) return PL M = int(input()) N = int(input()) C = list(map(int, input().split())) PL = PrimeList(M) PLS = set(PL) dp = [-1] * (M + 1) dp[M] = 0 for c in C: for i in reversed(range(c, M + 1)): if dp[i] != -1: dp[i - c] = max(dp[i - c], dp[i] + 1) maxv = max(dp) ans = maxv for i in range(M + 1): if i in PLS and dp[i] != -1: ans += dp[i] print(ans)