#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(){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>(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);}}