#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

#define nmax 300005
#define Nmax2 ((5*20)+1)
#define Pmax 21
#define Kmax 6

int V[Nmax2], dp[Kmax][Pmax], a[nmax], acum[Kmax][Pmax];
vector<int> lista[Pmax][Pmax];//va avea maxim 5 elemente
int n, m;

bool cmp(int a, int b){

    return a > b;

}

void citeste(){

    f >> n >> m;
    for(int i=1; i<=n; i++){
        f >> a[i];
    }

    sort(a+1, a+n+1, cmp);

}

void preprocesare(){

    //ma intereseaza pentru fiecare stare(P, rest) primele 5(deoarece Kmax =5) valori(in ordine descrescatoare) ce dau restul rest la impartirea cu P
    for(int i=1; i<=n; i++){
        for(int p=2; p<Pmax; p++){
            if (lista[p][ p%a[i] ].size() >= 5) continue;//daca am deja 5 elemente
            lista[p][ a[i]%p ].push_back( a[i] );//daca inca nu am il pun pe asta;
        }
    }


}

void initializeaza(){

    for(int k=0; k<Kmax; k++){
        for(int p=0; p<Pmax; p++) dp[k][p] = 0;
    }

    for(int i=0; i<Nmax2; i++) V[i] = 0;

}

void rezolva(){

    preprocesare();
    //pentru fiecare pereche de K,P fac un dp[i][j] = suma maxima avand i elemente care dau restul j la impartirea cu P;
    //ma folosesc de lista[p][rest]
    //fac un nou vector V[] = cu maxim 100 de elemnte(P*5); pentru ca ma intereseaza doar primele 5 valori pentru fiecare rest(evident primele 5 cele mai mari)

    for(int i=1; i<=m; i++){
        int K, P;
        f >> K >> P;

        initializeaza();
        V[0] = 0;
        for(int rest=0; rest<P; ++rest){
            for(int j=0; j<lista[P][rest].size(); j++){
                V[++V[0]] = lista[P][rest][j];
            }
        }
        //si acum fac dinamica
        for(int i=1; i<=V[0]; i++){//incerc sa ma bag si elementul V[i]
            //fac dinamica astfel : pornesc de la K-1 spre 0 si voi fi in starea dp[k][rest]; acum voi incerca sa actulizez dp[k+1][new_rest] folosindu-ma de V[i]
            //astfel nu ma voi mai folosi de o stare actulizara la pasul i

            for(int k=K-1; k>=0; --k){
                for(int rest=0; rest<P; rest++){
                    if (dp[k][rest] == 0) continue; //daca nu am obtinut restul pana acum
                    dp[k+1][ (rest+V[i]) % P ] = max( dp[k+1][ (rest+V[i]) %P ], dp[k][rest] + V[i] );
                }
            }

            if (dp[1][ V[i]%P ] == 0) dp[1][ V[i]%P ] = V[i];//cazul cand il iau singur pe V[i];

        }

        if (dp[K][0] == 0){
            g << "-1" << "\n";
        }else g << dp[K][0] << "\n";

    }


}

int main(){

    citeste();
    rezolva();

    f.close();
    g.close();

    return 0;

}