#!ruby -narprime
eval"*X,N,K,B="+$F*?,
B&&(N.times{X<<1+(X[-1].*X[-1]+12345)%(1e8+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)