#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];
vector<int> lista[Pmax][Pmax];
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(){
    for(int i=1; i<=n; i++){
        for(int p=2; p<Pmax; p++){
            if (lista[p][ a[i]%p ].size() >= 5) continue;
            lista[p][ a[i]%p ].push_back( a[i] );
        }
    }
 
 
}
 
void initializeaza(){
 
    for(int k=0; k<Kmax; k++){
        for(int p=0; p<Pmax; p++) dp[k][p] = 0;
    }
 
 
 
}
 
void rezolva(){
 
    preprocesare();
    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];
            }
        }

        for(int i=1; i<=V[0]; i++){
 
            for(int k=K-1; k>=0; --k){
                for(int rest=0; rest<P; rest++){
                    if (dp[k][rest] == 0) continue;
                    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];
 
        }
 
        if (dp[K][0] == 0){
            g << "-1" << "\n";
        }else g << dp[K][0] << "\n";
 
    }
 
 
}
 
int main(){
 
    citeste();
    rezolva();
 
    f.close();
    g.close();
 
    return 0;
 
}