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

using namespace std;

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

const int nmax= 300000;
const int kmax= 5;
const int pmax= 20;

int x[nmax+1], d[kmax+1][pmax], aux[kmax*pmax+1];

vector <int> v[pmax+1][kmax];

int main(  ) {
    int n, m;
    fin>>n>>m;
    for ( int i= 1; i<=n; ++i ) {
        fin>>x[i];
    }
    sort( x+1, x+n+1 );

    for ( int i= n; i>=1; --i ) {
        for ( int j= 2; j<=pmax; ++j ) {
            if ( (int)v[j][x[i]%j].size()<kmax ) {
                v[j][x[i]%j].push_back(x[i]);
            }
        }
    }

    for ( int cnt= 1; cnt<=m; ++cnt ) {
        int k, p, nr= 0;
        fin>>k>>p;
        for ( int i= 0; i<=p-1; ++i ) {
            for ( int j= 0; j<(int)v[p][i].size() && j<k; ++j ) {
                aux[++nr]= v[p][i][j];
            }
        }
        for ( int cnr= 1; cnr<=nr; ++cnr ) {
            for ( int i= k; i>=2; --i ) {
                for ( int j= 0; j<=p-1; ++j ) {
                    d[i][j]= max(d[i][j], aux[cnr]+d[i-1][(j+p-aux[cnr]%p)%p]);
                }
            }
            d[1][aux[cnr]%p]= max(d[1][aux[cnr]%p], aux[cnr]);
        }

        if ( d[k][0]==0 ) {
            d[k][0]= -1;
        }
        fout<<d[k][0]<<"\n";
        for ( int i= 0; i<=kmax; ++i ) {
            for ( int j= 0; j<=pmax-1; ++j ) {
                d[i][j]= 0;
            }
        }
    }

    return 0;
}