#import <bits/stdc++.h>
#define h(a,c)for(a=0;a<c;a++)
#define w d[5-j][(n+a[p][i])%p]
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,21){j=k;h(i,5&&p&&j>a[p][j%p*5+i])swap(a[p][j%p*5+i],j);}while(m--){f>>k>>p;h(i,120)d[++i%6][i--/6]=-1e7;h(i,100)h(j,5&&a[p][i])h(n,p)w=max(w,d[4-j][n]+a[p][i]);g<<max(d[k][0],-1)<<'\n';}}