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