#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#define MAXN 300010
using namespace std;
int v[MAXN];
vector<int> g[22][22];
int temp[110],dp[22][22];
int main(){
    freopen("tricouri.in","r",stdin);
    freopen("tricouri.out","w",stdout);
    int n,m,i,j,l,q,k,p,howMany;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
        scanf("%d",&v[i]);
    sort(v+1,v+n+1);
    for(i=n;i>=1;i--)
        for(j=2;j<=20;j++)
            if(g[j][v[i]%j].size()<5)
                g[j][v[i]%j].push_back(v[i]);
    for(q=1;q<=m;q++){
        scanf("%d%d",&k,&p);
        howMany=0;
        for(i=0;i<=p-1;i++)
            for(j=0;j<g[p][i].size()&&j<k;j++){
                howMany++;
                temp[howMany]=g[p][i][j];
            }
        for(l=1;l<=howMany;l++){
            for(i=k;i>=2;i--)
                for(j=0;j<=p-1;j++)
                    dp[i][j]=max(dp[i][j],temp[l]+dp[i-1][(j+p-temp[l]%p)%p]);
            dp[1][temp[l]%p]=max(dp[1][temp[l]%p],temp[l]);
        }
        if(dp[k][0]==0)
            printf("-1\n");
        else
            printf("%d\n",dp[k][0]);
        memset(dp,0,sizeof(dp));
    }
    return 0;
}