#include <bits/stdc++.h>
#define h(a,b,c)for(a=b;a<c;a++)
#define w(a,b)a=max(a,b)
using namespace std;
ifstream f("tricouri.in");
ofstream g("tricouri.out");
int i,n,m,a[21][121],j,k,x,p,d[6][21];
int main()
{
f>>n>>m;
while(n--&&f>>x)h(p,2,21){j=x;h(i,0,5)if(j>a[p][j%p*5+i])swap(a[p][j%p*5+i],j);}
while(m--){
f>>k>>p;h(i,1,120)d[i%6][i/6]=-1<<26;
h(i,0,100)for(j=5;a[p][i]&&j--;)h(n,0,p)w(d[j+1][(n+a[p][i])%p],d[j][n]+a[p][i]);
g<<max(d[k][0],-1)<<'\n';
}
}