#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';}}