#include<fstream.h>
ifstream f("tricouri.in");
ofstream g("tricouri.out");
 long i,j,n,k,max,l,v[300000];
 short int p,k1,m,b[1000000];
int main()
{
f>>n>>m;
for(i=1;i<=n;i++)
f>>v[i];
for(l=1;l<=m;l++)
{
f>>k1>>p;
for(i=1;i<=1000;i++)
b[i]=0;
max=0;
b[0]=1;
for(i=1;i<=n;i++)
for(j=max;j>=0;j--)
if(j==0)
{
if(v[i]>max)
max=v[i];
b[v[i]]=1;

}
else
if(b[j]>0)
if((b[j+v[i]]==0||b[j+v[i]]>b[j]+1)&&(b[j]<k1))
{b[j+v[i]]=b[j]+1;
if(j+v[i]>max)
max=v[i]+j;
}
i=i;
for(i=max;i>=1;i--)
if(i%p==0&&b[i]==k1)
{
g<<i<<'\n';
break;
}
if(i==0)
g<<"-1"<<'\n';
}
f.close();
g.close();
return 0;
}