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