#!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|f=->t{t%a>0?0:1+f[t/a]};X.map{|t|f[t]}.min(K).sum/z}.min)