#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;

const int NMAX = 300010;

int N, M, K, P, V[NMAX], S[110], Dp[6][21];
vector<int> List[21][21];

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

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

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

    for(int i = 1; i <= N; ++ i)
        for(int j = 2; j <= 20; ++ j)
            if(List[j][V[i] % j].size() < 5)
                List[j][V[i] % j].push_back(V[i]);

    for(; M; M --)
    {
        scanf("%i %i", &K, &P);

        for(int i = 0; i <= 5; ++ i)
            for(int j = 0; j <= 20; ++ j)
                Dp[i][j] = 0;
        S[0] = 0;

        for(int i = 0; i < P; ++ i)
            for(int j = 0; j < List[P][i].size(); ++ j)
                S[++S[0]] = List[P][i][j];

        for(int i = 1; i <= S[0]; ++ i)
        {
            for(int j = K - 1; j >= 0; -- j)
                for(int k = 0; k < P; ++ k)
                    if(Dp[j][k] != 0)
                        Dp[j + 1][(k + S[i]) % P] = max(Dp[j + 1][(k + S[i]) % P], Dp[j][k] + S[i]);
            if(Dp[1][S[i] % P] == 0) Dp[1][S[i] % P] = S[i];
        }

        if(Dp[K][0] == 0) printf("-1\n");
        else printf("%i\n", Dp[K][0]);
    }

    return 0;
}