#include <stdio.h>
#define MAXK 5
#define MAXP 20
#define MAXN 300000
#define INF 1000000000
int d[MAXP][MAXK+1][MAXP], e[MAXP+1][MAXP][MAXK];
int main(){
    int n, q, i, j, k, p, s, t, r, x, aux;
    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", &x);
        for(j=2; j<=MAXP; j++){
            if(x>e[j][x%j][MAXK-1]){
                e[j][x%j][MAXK-1]=x;
            }
            k=MAXK-1;
            while((k>0)&&(e[j][x%j][k-1]<e[j][x%j][k])){
                aux=e[j][x%j][k-1];
                e[j][x%j][k-1]=e[j][x%j][k];
                e[j][x%j][k]=aux;
                k--;
            }
        }
    }
    while(q>0){
        q--;
        fscanf(fin, "%d%d", &k, &p);
        for(i=0; i<MAXP; i++){
            for(j=0; j<=MAXK; j++){
                for(t=0; t<MAXP; t++){
                    d[i][j][t]=-INF;
                }
            }
        }
        d[0][0][0]=0;
        j=0;
        s=0;
        while((j<k)&&(e[p][0][j]!=0)){
            s+=e[p][0][j];
            j++;
            d[0][j][s%p]=s;
        }
        for(i=1; i<p; i++){
            for(t=0; t<=k; t++){
                for(r=0; r<p; r++){
                    d[i][t][r]=d[i-1][t][r];
                }
            }
            j=0;
            s=0;
            while((j<k)&&(e[p][i][j]!=0)){
                s+=e[p][i][j];
                j++;
                for(t=j; t<=k; t++){
                    for(r=0; r<p; r++){
                        if(d[i][t][(r+i*j)%p]<d[i-1][t-j][r]+s){
                            d[i][t][(r+i*j)%p]=d[i-1][t-j][r]+s;
                        }
                    }
                }
            }
        }
        if(d[p-1][k][0]<=0){
            d[p-1][k][0]=-1;
        }
        fprintf(fout, "%d\n", d[p-1][k][0]);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}