#include <bits/stdc++.h>
#define maxn 16005
#define maxp 25

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

std::vector <int> v[maxp][maxp];
std::vector <int> arr;
std::vector <int> x;

int dp[2][maxp][maxp];

int main()
{
    int n, Q, p=20, rest, K, k, i;
    fin >> n >> Q;
    x.resize(n);
    for (i=0; i<n; i++)
        fin >> x[i];
    std::sort (x.begin(), x.end());
    for (i=x.size()-1; i>=0; i--){
        for (p=2; p<=20; p++){
            rest = x[i] % p;
            if (v[p][rest].size() < 5)
                v[p][rest].push_back (x[i]);
        }
    }

    while (Q --){
        fin >> K >> p;
        arr.clear();
        for (rest=0; rest<p; rest++){
            for (auto it:v[p][rest])
                arr.push_back (it);
        }
        std::sort (arr.begin(), arr.end(), std::greater<int>());

        memset (dp, 0, sizeof dp);

        //for (auto i:arr)
        //    fout << i << '\n';

        int last = 0, crt = 1;

        dp[last][0][0] = 1;

        for (i=0; i<arr.size(); i++){
            memset (dp[crt], 0, sizeof dp[crt]);
            for (rest=0; rest<p; rest++){
                dp[crt][0][rest] = std::max (dp[crt][0][rest], dp[last][0][rest]);
                for (int k=1; k<=K; k++){
                    dp[crt][k][rest] = std::max (dp[crt][k][rest], dp[last][k][rest]);
                    if (dp[last][k-1][rest] == 0)
                        continue;

                    dp[crt][k][(rest+arr[i])%p] = std::max (dp[crt][k][(rest+arr[i])%p], dp[last][k-1][rest] + arr[i]);
                }
            }
            std::swap (last, crt);
        }

        fout << dp[last][K][0] - 1 << '\n';

    }


    return 0;
}