#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;
    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]--;
            }
        }
    }
    for(i = 1;i <= q;i++){
        scanf("%d %d",&k,&p);
        mx = -1;
        bkt(1);
        printf("%d\n",mx);
    }
    return 0;
}