#include <bits/stdc++.h>
using namespace std;
ifstream f("tricouri.in");
ofstream g("tricouri.out");
const int nMax = 300002;
int a[nMax], dp[2][6][20], val[nMax];
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 >> x;
        for(int j = 1; j <= 20; j++) {
            S[j][x%j].insert(x);
        }
    }

    sol = new int *[21];
    for(int i = 2; i <= 20; i++) {
        n = 0;
        for(int rest = 0; rest < i; rest++) {
            auto it = S[i][rest].rbegin();
            auto send = S[i][rest].rend();
            for(int cnt = 1; cnt <= 5 && it != send; cnt++) {
                a[++n] = *it;
            }
        }
        sol[i] = Builddp(n, 5, i);
    }
    while(m--) {
        f >> k >> p;
        g<< sol[p][k] << "\n";
    }
    return 0;
}