#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;){if(!A[p][i][j])return;x+=A[p][i][j];h(k-j++-1,x,i+1);}}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';}}