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

using namespace std;

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

const int NMAX = 300000, inf= 1<<30;

int a[NMAX+1] ;

vector <int> v[21][21];

int d[20][6][20];

void init(int t)
{
    for( int i= 0; i<20; ++i )
    {
        for( int j= 0; j<=5; ++j  )
        {
            for( int k= 0; k<=19; ++k )
            {
                d[i][j][k]= -inf;
            }
        }
    }
    d[0][0][0]= 0;
    for( int i=0; i<(int)v[t][0].size(); ++i )
    {
        d[0][i+1][0]= d[0][i][0]+v[t][0][i];
    }
}

int main(  )
{
    int N, M;
    in >> N >> M;
    for( int i= 1; i<=N; ++i )
    {
        in >> a[i];
    }

    sort( a+1, a+N+1 );

    for( int i= N; i>=1; --i )
    {
        for( int j= 2; j<=20; ++j )
        {
            if( v[j][ a[i]%j ].size()<5  ) v[j][ a[i]%j ].push_back( a[i] );
        }
    }

    int p, t;

    for( int Q= 1; Q<=M; ++Q )
    {
        in >> p >> t;
        init( t );
        for( int i= 0; i<t; ++i )
        {
            for( int j= 0; j<=p; ++j )
            {
                for( int k=0; k<t; ++k )
                {
                    d[i+1][j][k] = max( d[i+1][j][k], d[i][j][k]);
                    int auxsum = 0;
                    for( int x= 0; x<(int)v[t][i+1].size() && j+x+1<=p; ++x )
                    {
                        auxsum += v[t][i+1][x];
                        d[i+1][ j+x+1 ][ (k+(x+1)*(i+1))%t ]= max( d[i+1][ j+x+1 ][ (k+(x+1)*(i+1))%t ], d[i][j][k]+auxsum );
                    }
                }
            }
        }
        if( d[t-1][p][0]<0 ) out << "-1" << '\n';
        else out << d[t-1][p][0] << '\n';
    }

    return 0;
}