require 'prime'

n, m = 2.times.map{gets.to_i}
c = gets.split.map(&:to_i).sort
dp = Array.new(n + 1)
dp[n] = 0
c.each do |d|
    n.downto(0) do |i|
        if dp[i] && i - d >= 0
            if dp[i - d]
                dp[i - d] = dp[i] + 1 if dp[i - d] <= dp[i]
            else
                dp[i - d] = dp[i] + 1
            end
        end
    end
end
puts Prime.each(n).map {|pr| dp[pr] || 0 }.inject(0, &:+) + dp.compact.max