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