#include <fstream>
#include <algorithm>
#include <cstring>

#define In "tricouri.in"
#define Out "tricouri.out"
#define Kmax 7
#define Pmax 22
#define Nmax 300002

using namespace std;
int dp[Pmax][Kmax][Pmax];
/**
dp[i][j][k] = suma maxima a unei submultimi cu j elemente a.i. dp[i][j][k]%i = k
*/
int v[Nmax], a[102],p , cnt[Pmax];

inline void Dinamic()
{
    int i, ii, y, l, j, x, d[2][Kmax][Pmax];
    memset(d,0,sizeof(d));
    /**
    d[i][j][k] = suma maxima folosind j elemente din primele i a.i. d[i][j][k]%p = k
    */
    d[1][1][a[1]%p] = a[1];
    for(ii = 2,l = 0;ii <= a[0]; ++ii,l ^= 1)///luam fiecare element in parte ca la problema rucsacului
    {
        y = a[ii]%p;
        for(i = 1;i <= 5; ++i)///numarul de elemente
            for(j = 0; j < p; ++j)///restul
            {
                d[l][i][j] = d[l^1][i][j];
                x = j-y;
                if(x<0)
                    x += p;
                if(d[l^1][i-1][x])
                    d[l][i][j] = max(d[l][i][j],d[l^1][i-1][x]+a[ii]);
            }
    }
    memcpy(dp[p],d[a[0]&1],sizeof(d[a[0]&1]));
}
int main()
{
    int n, m, i, k;
    ifstream f(In);
    f>>n>>m;
    for(i = 1;i <= n; ++i)
        f>>v[i];
    sort(v + 1,v + n + 1,greater< int >() );
    for(p = 2;p <= 20; ++p)
    {
        a[0] = 0;
        for(i = 1;i <= n; ++i)
            if(cnt[v[i]%p]< 5)
            {
                a[++a[0]] = v[i];
                ++cnt[v[i]%p];
            }
        Dinamic();
        memset(cnt,0,sizeof(cnt));
    }
    ofstream g(Out);
    for(i = 1;i <= m; ++i)
    {
        f>>k>>p;
        if(dp[p][k][0])
            g<<dp[p][k][0]<<"\n";
        else
            g<<"-1\n";
    }
    f.close();
    g.close();
    return 0;
}