#include <cstdio>
#include <algorithm>
#include <cstring>
#define maxN 3000002
#define maxP 20
#define maxK 5
#define inf 300000000000LL
using namespace std;
int n, m, i, j, k, p, x;
long long dp[maxK][maxP + 1][maxP];
void read()
{
    freopen("tricouri.in", "r", stdin);
    scanf("%d %d", &n, &m);
    for (k = 0; k <= maxK; ++ k)
        for (p = 2; p <= maxP; ++ p)
                for (j = 1; j < p; ++ j)
                    dp[k][p][j] = -inf;

    for (i = 1; i <= n; ++ i)
    {
        scanf("%d", &x);
        for (k = min(i, maxK); k >= 1; -- k)
            for (p = 2; p <= maxP; ++ p)
                for (j = 0; j < p; ++ j)
                    dp[k][p][(j + x) % p] = max(dp[k][p][(j + x) % p], dp[k - 1][p][j] + x);
    }
}
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();
    write();
    return 0;
}