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