#include <fstream>
#define z(i, s, d) for (i = s; i < d; ++i)
std::fstream f("tricouri.in"), g("tricouri.out", std::_S_out);
int k, p, caca1, l, caca, w, A[32][32][8], s;
int n, m, i, j, a[32][32][8];

void h(int k, int x, int p)
{
  if (p == w)
  {
    if (!k && s < x && x % w == 0)
      s = x;
    return;
  }
  h(k,x,p + 1);
  for(j=0;j<k;j++)
  {
    if(!A[w][p][j])return;
    x+=A[w][p][j];
    h(k-j-1,x,p+1);
  }
}
main()
{
  f >> n >> m;
  for (i=0;i<n;i++) {
    f>>k;
    for (j=2;j<21;j++) {
      w=k%j;
      for(l=5;l&&k>a[j][w][l-1];l--)
        a[j][w][l] = a[j][w][l-1];
      a[j][w][l] = j;
    }
  }
  for(i=0;i<m;i++) {
    f>>k>>w;
    s=-1;
    h(k,0,0);
    g<<s<<'\n';
  }
}