#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+=n,i+1)){n=A[p][i][j];if(!n)return;}}main(){f>>n>>m;for(;n--;){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(;m--;g<<s<<'\n'){f>>k>>p;s=-1;h(k,0,0);}}