#include <cstdio>
#include <algorithm>
#include <vector>

#define NMAX 7
#define MMAX 27

using namespace std;

vector< int > H[NMAX][MMAX], v;
int D[NMAX][MMAX];
int n, Q, X[300007];

inline int Cmp(int a, int b){
    return a > b;
}

int main(){
    freopen("tricouri.in", "r", stdin);
    freopen("tricouri.out", "w", stdout);
    scanf("%d %d", &n, &Q);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &X[i]);
    sort(X + 1, X + n + 1, Cmp);
    for(int i = 1; i <= n; ++i)
        for(int j = 2; j <= 20; ++j)
            if(H[j][X[i] % j].size() < 5)
                H[j][X[i] % j].push_back(X[i]);
    for(; Q > 0; -- Q){
        int k = 0, p = 0;
        scanf("%d %d", &k, &p);
        for(int i = 0; i <= k; ++i)
            for(int j = 0; j <= p; ++j)
                D[i][j] = 0;
        v.clear();
        for(int i = 0; i <= p; ++i)
            for(vector< int >::iterator it = H[p][i].begin(); it != H[p][i].end(); ++it)
                v.push_back(*it);
        for(int i = 0; i < v.size(); ++i){
            for(int j = k - 1; j >= 0; --j)
                for(int l = 0; l < p; ++l)
                    if(D[j][l] != 0)
                        D[j + 1][(l + v[i]) % p] = max(D[j][l] + v[i], D[j + 1][(l + v[i]) % p]);
            if(D[1][v[i] % p] == 0)
                D[1][v[i] % p] = v[i];
        }
        if(D[k][0] == 0)
            D[k][0] = -1;
        printf("%d\n", D[k][0]);
    }
    return 0;
}