#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;fstream f("tricouri.in"),g("tricouri.out",_S_out);int i,n,m,a[21][121],j,k,p,d[6][21];main(){f>>n>>m;while(n--&&f>>k)h(p,2,21){j=k;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]=-1e7;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';}}