#include <cstdio>
#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][25];
int used[25],k,p,mx;
int usin[25];
int ju[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;
            ju[i]++;
            if(ju[i] <= h[p][i][0]){
                bkt(step+1);
            }
            ju[i]--;
        }
    }
}

int v[300005];

int main(){
    int n,q,i,j,x,l;
    freopen("tricouri.in", "r", stdin);
    freopen("tricouri.out", "w", stdout);
    scanf("%d %d",&n,&q);
    for(i = 1;i <= n;i++){
        scanf("%d",&v[i]);
    }
    sort(v+1, v+n+1);
    for(j = 2;j <= 20;j++){
        int nr = j;
        for(i = n;i >= 1;i--){
            x = v[i];
            if(h[j][x%j][0] < 5){
                h[j][x%j][++h[j][x%j][0]] = x;
                if(h[j][x%j][0] == 5){
                    nr--;
                }
            }
            if(nr == 0){
                break;
            }
        }
    }
    for(i = 1;i <= q;i++){
        scanf("%d %d",&k, &p);
        mx = -1;
        bkt(1);
        printf("%d\n",mx);
    }
    return 0;
}