#include <cstdio>
#include <math.h>
#include <algorithm>

using namespace std;
#define llu long long unsigned
#define ll long long
#define pb push_back
#define mp make_pair

//string problemName = "tricouri";
//string inFile = problemName+".in";
//string outFile = problemName+".out";
//ifstream fin(inFile.c_str());
//ofstream fout(outFile.c_str());

int h[25][25][10];
int used[25],k,p,mx;
int usin[25];

void bkt(int step){
    if(step == k){
        int i;
        int ret = 0;
        for(i = 1;i < k;i++){
            if(used[usin[i]]+1 <= h[p][usin[i]][0]){
                ret += h[p][usin[i]][++used[usin[i]]];
            }else{
                for(i = 1;i <= k;i++){
                    used[usin[i]] = 0;
                }
                return;
            }
        }
        usin[k] = p - ret%p;
        usin[k] %= p;
        if(used[usin[k]]+1 > h[p][usin[k]][0]){
            for(i = 1;i <= k;i++){
                used[usin[i]] = 0;
            }
            return;
        }
        ret += h[p][usin[k]][++used[usin[k]]];
        for(i = 1;i <= k;i++){
            used[usin[i]] = 0;
        }
        if(ret%p == 0 && ret){
            mx = max(mx, ret);
        }
    }else{
        int i;
        for(i = 0;i < p;i++){
            usin[step] = i;
            bkt(step+1);
        }
    }
}

int main(){
    int n,q,i,j,x,l,id,jd;
    freopen("tricouri.in", "r", stdin);
    freopen("tricouri.out", "w", stdout);
    scanf("%d %d",&n,&q);
    for(i = 1;i <= n;i++){
        scanf("%d",&x);
        for(j = 2;j <= 20;j++){
            h[j][x%j][++h[j][x%j][0]] = x;
            for(l = h[j][x%j][0];l > 1;l--){
                if(h[j][x%j][l] > h[j][x%j][l-1]){
                    swap(h[j][x%j][l], h[j][x%j][l-1]);
                }
            }
            h[j][x%j][6] = 0;
            if(h[j][x%j][0] > 5){
                h[j][x%j][0]--;
            }
        }
    }
    int test;
    bool ok;
    for(test = 1;test <= q;test++){
        scanf("%d %d",&k,&p);
        mx = -1;
        for(i = 0;i < p;i++){
            if(k == 1){
                int ret = 0;
                ok = true;
                for(jd = 1;jd < k;jd++){
                    if(used[usin[jd]]+1 <= h[p][usin[jd]][0]){
                        ret += h[p][usin[jd]][++used[usin[jd]]];
                    }else{
                        for(jd = 1;jd <= k;jd++){
                            used[usin[jd]] = 0;
                        }
                        ok = false;
                    }
                }
                usin[k] = p - ret%p;
                usin[k] %= p;
                if(used[usin[k]]+1 > h[p][usin[k]][0]){
                    for(i = jd;jd <= k;jd++){
                        used[usin[jd]] = 0;
                    }
                    ok = false;
                }
                ret += h[p][usin[k]][++used[usin[k]]];
                for(jd = 1;jd <= k;jd++){
                    used[usin[jd]] = 0;
                }
                if(ret%p == 0 && ret && ok){
                    mx = max(mx, ret);
                }
            }else{
                usin[1] = i;
                for(j = 0;j < p;j++){
                    if(k == 2){
                        int ret = 0;
                        ok = true;
                        for(jd = 1;jd < k;jd++){
                            if(used[usin[jd]]+1 <= h[p][usin[jd]][0]){
                                ret += h[p][usin[jd]][++used[usin[jd]]];
                            }else{
                                for(jd = 1;jd <= k;jd++){
                                    used[usin[jd]] = 0;
                                }
                                ok = false;
                            }
                        }
                        usin[k] = p - ret%p;
                        usin[k] %= p;
                        if(used[usin[k]]+1 > h[p][usin[k]][0]){
                            for(i = jd;jd <= k;jd++){
                                used[usin[jd]] = 0;
                            }
                            ok = false;
                        }
                        ret += h[p][usin[k]][++used[usin[k]]];
                        for(jd = 1;jd <= k;jd++){
                            used[usin[jd]] = 0;
                        }
                        if(ret%p == 0 && ret && ok){
                            mx = max(mx, ret);
                        }
                    }else{
                        usin[2] = j;
                        for(l = 0;l < p;l++){
                            if(k == 3){
                                int ret = 0;
                                ok = true;
                                for(jd = 1;jd < k;jd++){
                                    if(used[usin[jd]]+1 <= h[p][usin[jd]][0]){
                                        ret += h[p][usin[jd]][++used[usin[jd]]];
                                    }else{
                                        for(jd = 1;jd <= k;jd++){
                                            used[usin[jd]] = 0;
                                        }
                                        ok = false;
                                    }
                                }
                                usin[k] = p - ret%p;
                                usin[k] %= p;
                                if(used[usin[k]]+1 > h[p][usin[k]][0]){
                                    for(i = jd;jd <= k;jd++){
                                        used[usin[jd]] = 0;
                                    }
                                    ok = false;
                                }
                                ret += h[p][usin[k]][++used[usin[k]]];
                                for(jd = 1;jd <= k;jd++){
                                    used[usin[jd]] = 0;
                                }
                                if(ret%p == 0 && ret && ok){
                                    mx = max(mx, ret);
                                }
                            }else{
                                usin[3] = l;
                                for(id = 0;id < p;id++){
                                    if(k == 4){
                                        int ret = 0;
                                        ok = true;
                                        for(jd = 1;jd < k;jd++){
                                            if(used[usin[jd]]+1 <= h[p][usin[jd]][0]){
                                                ret += h[p][usin[jd]][++used[usin[jd]]];
                                            }else{
                                                for(jd = 1;jd <= k;jd++){
                                                    used[usin[jd]] = 0;
                                                }
                                                ok = false;
                                            }
                                        }
                                        usin[k] = p - ret%p;
                                        usin[k] %= p;
                                        if(used[usin[k]]+1 > h[p][usin[k]][0]){
                                            for(i = jd;jd <= k;jd++){
                                                used[usin[jd]] = 0;
                                            }
                                            ok = false;
                                        }
                                        ret += h[p][usin[k]][++used[usin[k]]];
                                        for(jd = 1;jd <= k;jd++){
                                            used[usin[jd]] = 0;
                                        }
                                        if(ret%p == 0 && ret && ok){
                                            mx = max(mx, ret);
                                        }
                                    }else{
                                        usin[4] = id;
                                        int ret = 0;
                                        ok = true;
                                        for(jd = 1;jd < k;jd++){
                                            if(used[usin[jd]]+1 <= h[p][usin[jd]][0]){
                                                ret += h[p][usin[jd]][++used[usin[jd]]];
                                            }else{
                                                for(jd = 1;jd <= k;jd++){
                                                    used[usin[jd]] = 0;
                                                }
                                                ok = false;
                                            }
                                        }
                                        usin[k] = p - ret%p;
                                        usin[k] %= p;
                                        if(used[usin[k]]+1 > h[p][usin[k]][0]){
                                            for(i = jd;jd <= k;jd++){
                                                used[usin[jd]] = 0;
                                            }
                                            ok = false;
                                        }
                                        ret += h[p][usin[k]][++used[usin[k]]];
                                        for(jd = 1;jd <= k;jd++){
                                            used[usin[jd]] = 0;
                                        }
                                        if(ret%p == 0 && ret && ok){
                                            mx = max(mx, ret);
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        printf("%d\n",mx);
    }
    return 0;
}