#include<fstream.h>
int m,put;
short int b[100000];
long n,i,j,k,max,p,v[20000];
ifstream f("tricouri.in");
ofstream g("tricouri.out");
int main()
{f>>n>>m;
for(i=1;i<=n;i++)
f>>v[i];
for(put=1;put<=m;put++)
{
for(i=1;i<=999;i++)
b[i]=0;
f>>k>>p;
max=0;
b[0]=1;
for(i=1;i<=n;i++)
{for(j=max;j>=0;j--)
if(j==0)
{b[v[i]]=1;
if(v[i]>max)
max=v[i];
}
else
if( b[j]>0)
if(b[j+v[i]]==0||b[j+v[i]]>b[j]+1)
{b[j+v[i]]=b[j]+1;
if(j+v[i]>max)
max=j+v[i];
}
}
for(i=max;i>0;i--)
if(b[i]==k&&i%p==0)
{g<<i;
break;}

if(i==0)
g<< "-1";
g<<"\n";
}
f.close();
g.close();
return 0;
}