#include <cstdio>
#include <algorithm>

#define DIM 300010
using namespace std;

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

int main () {

    freopen ("tricouri.in" ,"r", stdin );
    freopen ("tricouri.out","w", stdout);

    scanf ("%d %d", &N, &Q);

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

    for (int p = 2; p <= 20; p ++)
        D[0][p][0] = 0;

    for (int i = 1; i <= N; i ++)
        scanf ("%d", &V[i]);

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

    for (int i = N; i >=  1; i --) {
    for (int p = 2; p <= 20; p ++) {
        if (M[p][V[i]%p][0] < 5) {
            M[p][V[i]%p][++M[p][V[i]%p][0]] = V[i];
            sort (M[p][V[i]%p] + 1, M[p][V[i]%p] + M[p][V[i]%p][0] + 1);
        } else {
            M[p][V[i]%p][M[p][V[i]%p][0]] = V[i];
            sort (M[p][V[i]%p] + 1, M[p][V[i]%p] + M[p][V[i]%p][0] + 1);
        }
    }}

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

    for (int p = 2; p <= 20; p ++)
        D[0][p][0] = 0;


    for (int p = 2; p <= 20; p ++) {
        N = 0;
        for (int i = 0; i < p; i ++)
        for (int j = 0; j <= M[p][i][0]; j ++)
            V[++N] = M[p][i][j];

        for (int i = 1; i <= N; i ++) {
            for (int k = 4; k >= 0; k --) {
            for (int q = 0; q <  p; q ++) {
                if (D[k][p][q] != -1) {
                    if (D[k+1][p][(q+V[i])%p] < D[k][p][q] + V[i])
                        D[k+1][p][(q+V[i])%p] = D[k][p][q] + V[i];
                }
            }}
        }
    }

    for (int i = 1; i <= Q; i ++) {
        scanf ("%d %d", &K, &P);
        if (D[K][P][0] > 0)
            printf ("%d\n", D[K][P][0]);
        else
            printf ("-1\n");
    }

    return 0;
}