#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("tricouri.in");
ofstream g("tricouri.out");
int n,m;
int rez[21][21][6],a[300001],fol[21][21];
int main()
{
    f>>n>>m;
    for(int i=0;i<n;++i)
      f>>a[i];
    sort(a,a+n);
    for(int i=n-1;i>=0;--i)
    {
        int neimp=-1;
        for(int j=2;j<=20;++j)
        {
            ++fol[j][a[i]%j];
            if(fol[j][a[i]%j]<5)
              neimp=a[i];
        }
        a[i]=neimp;
    }
    for(int i=n-1;i>=0;--i)
    {
        if(a[i]==-1)
          continue;
        int x=a[i];
        for(int j=2;j<=20;++j)
          for(int k=4;k>=0;--k)
            for(int l=0;l<j;++l)
              if(((k==0)||rez[j][l][k])&&rez[j][(rez[j][l][k]+x)%j][k+1]<rez[j][l][k]+x)
                rez[j][(rez[j][l][k]+x)%j][k+1]=rez[j][l][k]+x;
    }
    for(int i=0;i<m;++i)
    {
        int x,y;
        f>>x>>y;
        if(!rez[y][0][x])
          g<<"-1\n";
        else
          g<<rez[y][0][x]<<"\n";
    }
    return 0;
}