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