#include <bits/stdc++.h>
using namespace std;
ifstream f("tricouri.in");
ofstream g("tricouri.out");
const int nMax = 300002;
int a[200], dp[2][6][20], val[nMax], v[nMax], cnt[7];
multiset <int> S[21][21];
int **sol;
inline int * Builddp(const int n, const int k,const int p) {
    int *sol = new int [6];
    int lin = 1;
    memset(dp,-1,sizeof(dp));
    dp[0][0][0] = 0;
    dp[1][0][0] = 0;
    for(int i = 1; i <= n; i++, lin = 1 - lin) {
        int x = a[i] % p;
        for(int j = 1; j <= k; j++) {
            for(int rest = 0; rest < p; rest++) {
                dp[lin][j][rest] = dp[1 - lin][j][rest];
                int r = rest - x;
                if(r < 0) {
                    r += p;
                }
                if(dp[1 - lin][j - 1][r] != -1)
                    dp[lin][j][rest] = max(dp[lin][j][rest], dp[1 - lin][j - 1][r] + a[i]);
            }
        }
    }
    for(int i = 1; i <= k; i++) {
        sol[i] = dp[1 - lin][i][0];
    }
    return sol;
}
int main()
{
    int n , m, k, p, x;
    f >> n >> m;
    for(int i = 1; i <= n; i++) {
        f >> v[i];
    }
    sort(v + 1, v + n + 1);
    sol = new int *[21];
    for(int i = 2; i <= 20; i++) {
        int dim = 0;
        for(int j = 0; j < i; j++) {
            cnt[j] = 0;
        }
        for(int j = n; j >= 1; j--) {
            if(cnt[v[j] % i] != 5) {
                cnt[v[j] % i]++;
                a[++dim] = v[j];
            }
        }
        sol[i] = Builddp(dim, 5, i);
    }
    while(m--) {
        f >> k >> p;
        g<< sol[p][k] << "\n";
    }
    return 0;
}