#include <fstream>
#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++){
            ret += h[p][usin[i]][++used[usin[i]]];
        }
        usin[k] = p - ret%p;
        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;
    fin>>n>>q;
    for(i = 1;i <= n;i++){
        fin>>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]--;
            }
        }
    }
    for(i = 1;i <= q;i++){
        fin>>k>>p;
        mx = -1;
        bkt(1);
        fout<<mx<<'\n';
    }
    return 0;
}