#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]
            for(int k=0; k<Kmax; k++){
                for(int p=0; p<Pmax; p++) acum[k][p] = 0;
            }

            for(int k=1; k<K; k++){
                for(int rest=0; rest<P; ++rest){
                    if (dp[k][rest] == 0) continue;//daca nu am reusit sa obtin restul rest avand k elemente
                    acum[k+1][ (rest+(V[i]%P) ) % P ] = dp[k][rest] + V[i];//mai folosesc inca o matrice pt a evita cazul
                    //cand dp[k+1][new_rest] se foloseste de V[i] si atunci la pasul urmator cand K = K+1 nu voi sti daca m-am folosit sau nu de V[i]
                    //sau mai e o varianta sa pornesc de la K sper 1; astfel nu voi mai avea nevoie de matricea "acum" pt ca
                    //voi incerca sa maximizez starea dp[k+1][new_rest](evident ajutandu-ma de V[i]) eu fiind in starea (k, rest);
                }
            }

            for(int k=1; k<=K; k++){
                for(int rest=0; rest<P; ++rest){
                    dp[k][rest] = max(dp[k][rest], acum[k][rest]);
                }
            }
            if (dp[1][ V[i]%P ] == 0) dp[1][ V[i]%P ] = 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;

}