#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;

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", &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 ++) {
        scanf ("%d %d", &K, &P);

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

    return 0;
}