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