#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
vector<int>v[25][25];
int x[300005],cnt[20],num[10],maxim=0,k,p,cnt2[20];
int back(int lvl){
if (lvl==k){
int sum=0,s=0,i;
for(i=1;i<=k-1;i++)
sum=(sum+num[i])%p;
sum=p-sum;
if (sum==p)
sum=0;
num[k]=sum;
cnt2[num[k]]++;
if (v[num[k]][p].size()<cnt2[num[k]])
return 0;
cnt2[num[k]]--;
memset(cnt,0,sizeof(cnt));
for(i=1;i<=k;i++){
s=s+v[num[i]][p][cnt[num[i]]];
cnt[num[i]]++;}
if (i==k+1)
if (maxim<s)
maxim=s;}
else{
for(int i=0;i<p;i++){
num[lvl]=i;
cnt2[num[lvl]]++;
if (v[num[lvl]][p].size()<cnt2[num[lvl]]){
cnt2[num[lvl]]--;
continue;}
back(lvl+1);
cnt2[num[lvl]]--;}
num[lvl]=0;}}
int main(){
freopen("tricouri.in","r",stdin);
freopen("tricouri.out","w",stdout);
int n,m,i,j;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
scanf("%d",&x[i]);
sort(x+1,x+n+1);
for(i=n;i>=1;i--)
for(j=2;j<=20;j++)
if (v[x[i]%j][j].size()<5)
v[x[i]%j][j].push_back(x[i]);
for(i=1;i<=m;i++){
scanf("%d%d",&k,&p);
maxim=0;
back(1);
if (maxim==0)
printf("-1\n");
else
printf("%d\n",maxim);}
return 0;}