#include <algorithm>
#include <fstream>
#include <string>

using namespace std;

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

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

int d[pmax+1][kmax+1], v[nmax+1], ch[pmax+1];

string buffer;
string::iterator buffer_it;

void read( int &x ) {
    for ( ; *buffer_it>'9' || *buffer_it<'0'; ++buffer_it ) ;
    for ( x= 0; *buffer_it<='9' && *buffer_it>='0'; ++buffer_it ) {
        x= x*10+*buffer_it-'0';
    }
}

void clear(  ) {
    for ( int i= 0; i<=pmax; ++i ) {
        for ( int j= 0; j<=kmax; ++j ) {
            d[i][j]= -1;
        }
    }
    for ( int i= 0; i<=pmax; ch[i]= 0, ++i ) ;
    d[0][0]= 0;
}

int main(  ) {
    getline( fin, buffer, (char)0 );
    buffer_it= buffer.begin();

    int n, m;
    read(n), read(m);
    for ( int i= 1; i<=n; ++i ) {
        read(v[i]);
    }
    sort( v+1, v+n+1 ) ;

    for ( clear(); m; --m, clear() ) {
        int k, p;
        read(k), read(p);
        for ( int l= n; l>=1; --l ) {
            if ( ch[v[l]%p]<=k-1 ) {
                ++ch[v[l]%p];

                for ( int i= 0; i<=p-1; ++i ) {
                    for ( int j= k-1; j>=0; --j ) {
                        if ( d[i][j]>=0 ) {
                            d[(i+v[l])%p][j+1]= max(d[(i+v[l])%p][j+1], d[i][j]+v[l]);
                        }
                    }
                }
            }
        }

        fout<<d[0][k]<<"\n";
    }

    return 0;
}