#include <cstdio>
#include <algorithm>
#include <cstring>
#define maxN 300002
#define maxP 20
#define maxK 5
#define inf 3000000000000LL
using namespace std;
int n, m, i, j, k, p, nr, v[maxN], w[maxN], no[maxP];
long long dp[maxK + 2][maxP + 2][maxP];
void read()
{
    freopen("tricouri.in", "r", stdin);
    scanf("%d %d", &n, &m);

    for (i = 1; i <= n; ++ i)
        scanf("%d", &v[i]);
}
void solve()
{
    sort(v + 1, v + n + 1);
    for (k = 0; k <= maxK; ++ k)
        for (p = 2; p <= maxP; ++ p)
                for (j = 1; j < p; ++ j)
                    dp[k][p][j] = -inf;

    for (p = 2; p <= maxP; ++ p)
        {
            nr = p;
            w[0] = 0;
            for (i = 0; i < p; ++ i)
                no[i] = 0;
            for (i = n; i >= 1; -- i)
            {
                if (no[v[i] % p] < maxK)
                {
                    w[++ w[0]] = v[i];
                    ++ no[v[i] % p];
                    if (no[v[i] % p] == maxK)
                        -- nr;
                }
                if (nr == 0)
                    break;
            }
            for (i = 1; i <= w[0]; ++ i)
                for (k = min(i, maxK); k >= 1; -- k)
                    for (j = 0; j < p; ++ j)
                        dp[k][p][(j + w[i]) % p] = max(dp[k][p][(j + w[i]) % p], dp[k - 1][p][j] + w[i]);
        }
}
void write()
{
    freopen("tricouri.out", "w", stdout);
    while (m --)
    {
        scanf("%d %d", &k, &p);
        if (dp[k][p][0] == 0)
            dp[k][p][0] = -1;
        printf("%lld\n", dp[k][p][0]);
    }
}
int main()
{
    read();
    solve();
    write();
    return 0;
}