#include<fstream.h>
ifstream f("tricouri.in");
ofstream g("tricouri.out");
 long i,j,n,k,max,l,v[3000];
 short int p,k1,m,u[100000][100],b[100000];
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;
for(k=1;k<=n;k++)
u[v[i]][k]=0;
u[v[i]][i]=1;
}
else
if(b[j]>0)
if((b[j+v[i]]==0||b[j+v[i]]>b[j]+1)&&(b[j]<k1)&&(u[j][i]==0))
{b[j+v[i]]=b[j]+1;
if(j+v[i]>max)
max=v[i]+j;
for(k=1;k<=n;k++)
u[j+v[i]][k]=u[j][k];
u[j+v[i]][i]=1;
}
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;
}