#!ruby -narprime
eval"*X,N,K,B=S="+$F*?,
B&&(N.times{X<<S=1+(S.*S+12345)%(10**8+9)};p B.prime_division.map{|a,z|X.map{|t|c=0;(c+=1;t/=a)while t%a<1;c}.min(K).sum/z}.min)