require'prime'
eval"M,N,*C="+$<.read.split*?,
d=[-M]*M<<r=0
p d.each{k=d[M];C.map{|j|j>M||d[M-j]>k||d[M-j]=k+1};M.prime?&&k>0&&r+=k;M-=1}.max+r