#include <cstdio>
#include <algorithm>
#include <cstring>

#define DIM 300010
#define INF 2000000000
using namespace std;

int N, Q, K, P, W[DIM], V[DIM], Nr[22];
int D[22][22][22], l, M;

class InputReader {
    public:
        InputReader() {}
        InputReader(const char *file_name) {
            input_file = fopen(file_name, "r");
            cursor = 0;
            fread(buffer, SIZE, 1, input_file);
        }
        inline InputReader &operator >>(int &n) {
            while(buffer[cursor] < '0' || buffer[cursor] > '9') {
                advance();
            }
            n = 0;
            while('0' <= buffer[cursor] && buffer[cursor] <= '9') {
                n = n * 10 + buffer[cursor] - '0';
                advance();
            }
            return *this;
        }
    private:
        FILE *input_file;
        static const int SIZE = 1 << 17;
        int cursor;
        char buffer[SIZE];
        inline void advance() {
            ++ cursor;
            if(cursor == SIZE) {
                cursor = 0;
                fread(buffer, SIZE, 1, input_file);
            }
        }
};

int main () {

    InputReader fin ("tricouri.in");
    freopen ("tricouri.out","w", stdout);

    fin >> N >> Q;

    for (int i = 1; i <= N; i ++)
        fin >> V[i];

    sort (V + 1, V + N + 1);

    for (int k = 0; k <=  5; k ++)
    for (int p = 2; p <= 20; p ++)
    for (int r = 1; r <   p; r ++)
        D[k][p][r] = -INF;

    for (int p = 2; p <= 20; p ++) {
        l = 0; M = 0;

        memset (Nr, 0, sizeof (Nr));
        for (int i = N; i >= 1; i --) {

            if (Nr[V[i] % p] < 5) {
                W[++M] = V[i];
                Nr[V[i] % p] ++;

                if (Nr[V[i] % p] == 5) {
                    // am completat toata lista cu elemente ce
                    // dau restul V[i] % p la impartirea cu p

                    l ++;
                }
            }

            if (l == p) {
                // am completat toate listele cu elemente ce
                // dau resturile 0-(p-1) la impartirea cu p

                break;
            }
        }


        for (int i = 1; i <= M; i ++)
        for (int k = 4; k >= 0; k --)
        for (int r = 0; r <  p; r ++)
            D[k+1][p][(r+W[i]) % p] = max (D[k+1][p][(r+W[i]) % p], D[k][p][r] + W[i]);
    }

    for (int q = 1; q <= Q; q ++) {
        fin >> K >> P;

        if (D[K][P][0] <= 0)
            printf ("-1\n");
        else
            printf ("%d\n", D[K][P][0]);
    }

    return 0;
}