#include <fstream>
#include <cstring>

using namespace std;

ifstream in ("tricouri.in");
ofstream out ("tricouri.out");

#define n 300001
#define k 6
#define p 21

int N, M, K, P, A[n], dp[k][n][p], Sol;

int main()
{
    int i, m, j, r, q;
    in >> N >> M;
    for (i = 1; i <= N; i++) in >> A[i];
    for (m = 1; m <= M; m++)
    {
        in >> K >> P;
        Sol = 0;
        memset (dp, 0, sizeof(dp));
        for (i = 1; i <= N; i++) dp[1][i][ A[i] % P ] = A[i];
        for (j = 1; j < K; j++)
        {
            for (i = j; i < N; i++)
            {
                for (r = 0; r < P; r++)
                {
                    for (q = i + 1; q <= N; q++)
                    {
                        if (dp[j][i][r] + A[q] > dp[j + 1][q][(r + A[q]) % P])
                        {
                            dp[j + 1][q][(r + A[q]) % P] = dp[j][i][r] + A[q];
                        }
                    }
                    //dp[j + 1][i + 1][(r + A[i + 1]) % P] += dp[j][i][r] + A[i + 1];
                }
            }
        }
        for (i = 1; i <= N; i++) if (dp[K][i][0] > Sol) Sol = dp[K][i][0];
        if (Sol == 0) out << -1 << '\n';
        else out << Sol << '\n';
    }
    return 0;
}