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

using namespace std;


int a[25][25][20];

int max;
int p,k;
int ver[20][20][20];
int i;
int j,m;
int n;
int s[10];
int l;
int marime;
int nr1;
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 = a[k][s[j]][0];
                        l = marime;
                        

                        while(ver[k][s[j]][l] != 0)
                        {
                                --l;
                                if (l <= 0)
                                {
                                        memset(ver,0,sizeof(ver));
                                        return ;
                                }
                        }
                        ver[k][s[j]][l] = 1;
                        sum += a[k][s[j]][l];
                }
                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);
        int x;
        for(i=1;i<=n;i++)
        {
                scanf("%d", &x);
                for(j = 2;j <= 20; ++j)
                {
                        nr1 = x % j;
                        k = 1;
                        while(k <= a[j][nr1][0] && a[j][nr1][k] < x )
                        {
                                ++k;
                        }
           //             printf("%d %d %d\n\n",nr1,k,a[j][nr1][0]);
                        if (k >= a[j][nr1][0])
                        {
                                a[j][nr1][0]++;
                                a[j][nr1][a[j][nr1][0]] = x;
                        }
                        else
                        {
                                for(l = 1;l <= k; ++l)
                                {
                                        a[j][nr1][l] = a[j][nr1][l+1];
                                }
                                a[j][nr1][k] = x;
                        }
                }
        }
        for( i = 1;i <= m; ++i)
        {
                scanf("%d %d",&p,&k);
                maxi = 0;
                bkt(1);
                if (maxi>0) printf("%d\n",maxi);
                        else
                        {
                                printf("-1\n");
                        }
        }
        return 0;
}