# include <cstdio>

const char *FIN = "tricouri.in", *FOU = "tricouri.out";
const int MAX_P = 21, MAX_K = 6;

int V[MAX_P][MAX_P][MAX_K], dp[MAX_P][MAX_K][MAX_P];
int N, M;

# define CT (p + j) % i

inline int max (int A, int B) {
    return (A > B ? A : B) ;
}

int main (void) {
    freopen (FIN, "r", stdin) ;
    freopen (FOU, "w", stdout) ;

    scanf ("%d %d", &N, &M) ;
    for (int i = 0, X; i < N; ++i) {
        scanf ("%d", &X);
        for (int j = 2; j < MAX_P; ++j) {
            int mod = X % j, min = X, pmin = 6;
            for (int k = 1; k < MAX_K; ++k) {
                if (V[j][mod][k] < min) {
                    min = V[j][mod][k], pmin = k;
                }
            }
            if (pmin < 6) V[j][mod][pmin] = X;
        }
    }
    for (int i = 2; i < MAX_P; ++i) {
        for (int j = 0; j < i; ++j) {
            for (int k = 1; k < MAX_K; ++k) {
                for (int l = 4; l + 1; --l) {
                    for (int p = 0; p < i; ++p) {
                        if (p == 0 || l > 0) {
                            dp[i][l + 1][CT] = max (dp[i][l + 1][CT], V[i][j][k] + dp[i][l][p]);
                        }
                    }
                }
            }
        }
    }
    for (int K, P; M; --M) {
        scanf ("%d %d", &K, &P);
        printf ("%d\n", dp[P][K][0] ? dp[P][K][0] : -1);
    }
}