#include<stdio.h>
#include<vector>
#include<algorithm>

using namespace std;

const int maxn = 300001;

vector <int> vect[40];

int max;
int p,k;
int i;
int j,m;
int s[maxn];
int n;
int l;
int a[maxn];
int ver[maxn];
int marime;
int maxi;


void bkt(int i)
{
        if (i<p)
        {
                for(s[i] = 0;s[i] <= k; ++s[i])
                {
                        bkt(i+1);
                }
        }
        else
        {

                int i1 = 1;
                int sum = 0;
                for(i1 = 1; i1 <= p-1 ; ++i1)
                        sum += s[i1];
                s[p]=(k-sum%k)%k;
                sum = 0;
                for(j = 1;j <= p; ++j )
                {
                        vector <int> :: iterator it;

                        marime = vect[s[j]].size();
                        l = 0;
                        
                        if (l == marime)
                        {

                                memset(ver,0,sizeof(ver));
                                return ;
                        }

                        it = vect[s[j]].begin();

                        while(ver[*it] != 0)
                        {
                                ++l;
                                if (l>=marime)
                                {
                                        memset(ver,0,sizeof(ver));
                                        return ;
                                }
                                ++it;
                        }
                        int f = a[*it];

                        sum += f;
                        ver[*it]=1;
                }
                if (sum > maxi)
                {
                        maxi = sum;
                }
                
        }
}

bool cmpf(const int &i,const int &b)
{
        return a[i]>a[b];
}


int main()
{
        freopen("tricouri.in","r",stdin);
        freopen("tricouri.out","w",stdout);
        scanf("%d %d",&n,&m);
        for(i=1;i<=n;i++)
        {
                scanf("%d", &a[i]);
        }
        for( i = 1;i <= m; ++i)
        {
                scanf("%d %d",&p,&k);
                maxi = 0;
                for(j = 1; j <= n; ++j)
                {
                        vect[a[j]%k].push_back(j);
                }
                for(j = 0;j <= k; ++j)
                {
                        sort(vect[j].begin(), vect[j].end(), cmpf);
                }
                bkt(1);
                for(j = 0; j <= k; ++j )
                {
                        vect[j].clear();

                }
                if (maxi>0) printf("%d\n",maxi);
                        else
                        {
                                printf("-1\n");
                        }
        }
        return 0;
}