import Control.Applicative
import Control.Monad
import Data.Array.ST
import Data.Array.Unboxed
import Data.Int

inf :: Integral a => a
inf = 1000000000

-- Based on <http://qiita.com/little_Haskeller/items/614a3ae20a517c19bb1f this article> .
primes2 :: Integral a => [a]
primes2 = [2, 3, 5] ++ sieve2 5 7 (drop 2 primes2)
    where
        sieve2 m s (p : ps) = [n | n <- ns, gcd m n == 1] ++ sieve2 (m * p) (p * p) ps
            where ns = [x + y | x <- [s, s + 6 .. p * p - 2], y <- [0, 4]]
        sieve2 _ _ [] = error "Unexpected"

-- Based on <https://wiki.haskell.org/Testing_primality this page> .
isPrime2 :: Integral a => a -> Bool
isPrime2 n = n > 1 && foldr (\p r -> p * p > n || (mod n p /= 0 && r)) True primes2

dpTable :: Int64 -> [Int64] -> UArray Int64 Int64
dpTable m cs = runSTUArray $ do
    dp <- newArray (0, m) (-inf)
    writeArray dp m 0
    forM_ cs $ \c ->
        forM_ [m - c, m - c - 1 .. 0] $ \i -> do
            term1 <- readArray dp i
            term2 <- readArray dp $ i + c
            writeArray dp i $ max term1 $ term2 + 1
    return dp

computeMaxCups :: Int64 -> [Int64] -> Int64
computeMaxCups m cs = s + maximum (elems dp)
    where
        dp = dpTable m cs
        s = sum [d | i <- [1 .. m], let d = dp ! i, d > 0, isPrime2 i]

main :: IO ()
main = do
    m <- readLn
    _ <- getLine
    cs <- fmap read . words <$> getLine
    print $ computeMaxCups m cs