#import<fstream>
std::fstream f("tricouri.in"),g("tricouri.out",std::_S_out);int n,k,p,i,j,s,A[32][32][8];void h(int k,int x,int i,int j=0){if(i-p)for(h(k,x,i+1);n=A[p][i][j],j<k&n;h(k-++j,x+=n,i+1));s=k|s>=x|x%p?s:x;}main(){for(f>>n>>s;n--;)for(f>>j,i=2;p=j%i,i<21;A[i++][p][k]=j)for(k=5;k&&j>(s=A[i][p][k-1]);A[i][p][k--]=s);for(;f>>k>>p;g<<s<<'\n')s=-1,h(k,0,0);}