#include <stdio.h>
#define MAXK 5
#define MAXP 20
#define MAXN 300000
#define INF 1000000000
int d[MAXP+1][MAXP*MAXK+1][MAXK+1][MAXP], e[MAXP][MAXK], v[MAXN+1], max[MAXP+1];
int main(){
    int n, q, i, j, k, x, aux, p, t, u;
    FILE *fin, *fout;
    fin=fopen("tricouri.in", "r");
    fout=fopen("tricouri.out", "w");
    fscanf(fin, "%d%d", &n, &q);
    for(i=1; i<=n; i++){
        fscanf(fin, "%d", &v[i]);
    }
    for(p=2; p<=MAXP; p++){
        for(i=0; i<p; i++){
            for(j=0; j<MAXK; j++){
                e[i][j]=0;
            }
        }
        for(i=1; i<=n; i++){
            x=v[i]%p;
            if(v[i]>e[x][MAXK-1]){
                e[x][MAXK-1]=v[i];
            }
            k=MAXK-1;
            while((k>0)&&(e[x][k-1]<e[x][k])){
                aux=e[x][k-1];
                e[x][k-1]=e[x][k];
                e[x][k]=aux;
                k--;
            }
        }
        for(k=0; k<=MAXP*MAXK; k++){
            for(t=0; t<=MAXK; t++){
                for(u=0; u<p; u++){
                    d[p][k][t][u]=-INF;
                }
            }
        }
        k=0;
        d[p][k][0][0]=0;
        for(i=0; i<p; i++){
            j=0;
            while((j<MAXK)&&(e[i][j]!=0)){
                k++;
                for(t=1; t<=MAXK; t++){
                    for(u=0; u<p; u++){
                        if(d[p][k][t][(u+i)%p]<d[p][k-1][t-1][u]+e[i][j]){
                            d[p][k][t][(u+i)%p]=d[p][k-1][t-1][u]+e[i][j];
                        }
                        if(d[p][k][t][u]<d[p][k-1][t][u]){
                            d[p][k][t][u]=d[p][k-1][t][u];
                        }
                    }
                }
                j++;
            }
        }
        max[p]=k;
    }
    for(i=0; i<q; i++){
        fscanf(fin, "%d%d", &k, &p);
        if(d[p][max[p]][k][0]<=0){
            d[p][max[p]][k][0]=-1;
        }
        fprintf(fout, "%d\n", d[p][max[p]][k][0]);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}