#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> List[25][25];
int N, M, K, P, X, Freq[25], Ans;

void Go(int Cnt, int SR)
{
    if(Cnt == K)
    {
        int RemR = P - SR, Sum = 0;
        Freq[RemR] ++;

        for(int i = 0; i < P; ++ i)
            if(Freq[i] != 0)
            {
                if(Freq[i] <= List[P][i].size())
                {
                    for(int j = 0; j < Freq[i]; ++ j)
                        Sum += List[P][i][j];
                }else
                {
                    Freq[RemR] --;
                    return ;
                }
            }
        Ans = max(Ans, Sum);
        Freq[RemR] --;
        return ;
    }

    for(int i = 0; i < P; ++ i)
    {
        if(List[P][i].size() <= Freq[i]) continue;
        Freq[i] ++;
        Go(Cnt + 1, (SR + i) % P);
        Freq[i] --;
    }
}

int main()
{
    freopen("tricouri.in", "r", stdin);
    freopen("tricouri.out", "w", stdout);

    scanf("%i %i", &N, &M);
    for(int i = 1; i <= N; ++ i)
    {
        scanf("%i", &X);
        for(int j = 2; j <= 20; ++ j)
        {
            int R = X % j;
            List[j][R].push_back(X);
            int P = List[j][R].size() - 1;
            while(P >= 1 && List[j][R][P - 1] < List[j][R][P]) swap(List[j][R][P - 1], List[j][R][P]), P --;
            if(List[j][R].size() > 5) List[j][R].pop_back();
        }
    }

    for(; M; M --)
    {
        scanf("%i %i", &K, &P);

        if(K == 1)
        {
            if(List[P][0].size() > 0) printf("%i\n", List[P][0][0]);
            else printf("-1\n");
            continue;
        }
        for(int i = 0; i < 20; ++ i) Freq[i] = 0;
        Ans = -1;
        Go(1, 0);
        printf("%i\n", Ans);
    }

    return 0;
}