#include <bits/stdc++.h>

using namespace std;

ifstream fin("tricouri.in");
ofstream fout("tricouri.out");

const int NMAX = 3e5;
const int KMAX = 8;
const int PMAX = 22;
int N, Q, init[NMAX], dp[2][KMAX][PMAX];
vector<int> v[PMAX][PMAX];

/// dp[i][j][r] - valoarea maxima ce o obtinem din primele i numere, avand primele j
///               resturi posibile la impartirea cu P si avand acum restul r

void max_self(int &a, int b) {
    a = max(a, b);
}

int main() {
    fin >> N >> Q;
    for(int i = 0; i < N; ++i)
        fin >> init[i];
    sort(init, init + N, greater<int>());
    for(int i = 0; i < N; ++i)
        for(int p = 2; p < 21; ++p) {
            int r = init[i] % p;
            if(v[p][r].size() < 5)
                v[p][r].emplace_back(init[i]);
        }
    for(int q = 0; q < Q; ++q) {
        int K, P;
        fin >> K >> P;
        vector<int> a;
        for(int r = 0; r < P; ++r)
            for(const int &x : v[P][r])
                a.emplace_back(x);
        sort(a.rbegin(), a.rend());
        memset(dp, 0, sizeof(dp));
        dp[0][0][0] = 1;
        int ind = 1;
        for(int i = 0; i < (int)a.size(); ++i, ind ^= 1) {
            memset(dp[ind], 0, sizeof(dp[ind]));
            for(int rest = 0; rest < P; ++rest) {
                max_self(dp[ind][0][rest], dp[ind ^ 1][0][rest]);
                for(int k = 1; k <= K; ++k) {
                    max_self(dp[ind][k][rest], dp[ind ^ 1][k][rest]);
                    if(dp[ind ^ 1][k - 1][rest] == 0)
                        continue;
                    max_self(dp[ind][k][(rest + a[i]) % P], dp[ind ^ 1][k - 1][rest] + a[i]);
                }
            }
        }
        fout << dp[ind ^ 1][K][0] - 1 << '\n';
    }
}