#include<cstdio>
#include<algorithm>
using namespace std;
const int M=300005;
int lung,baza,maxim,n,m,a[M],sol[21],v[21][21][6];
void read()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
}
bool comp(const int &x,const int &y)
{
    return (x>y);
}
void init()
{
    sort(a+1,a+n+1,comp);
    for(int b=1;b<=20;b++)
        for(int i=1;i<=n;i++)
            if(v[b][a[i]%b][0]<5)
                v[b][a[i]%b][++v[b][a[i]%b][0]]=a[i];
}
void solve()
{
    int sum=0;
    for(int i=1;i<lung;i++)
        sum+=sol[i];
    sum%=baza;
    sum=baza-sum;
    if(!v[baza][sum][0])
        return;
    int buline=0,ic[21];
    for(int i=0;i<21;i++)
        ic[i]=1;
    sol[lung]=sum;
    for(int i=1;i<=lung;i++)
        buline+=v[baza][sol[i]][ic[sol[i]]++];
    if(buline>maxim)
        maxim=buline;
}
void back(int poz)
{
    if(poz==lung)
    {
        solve();
        return;
    }
    for(int i=0;i<baza;i++)
        if(v[baza][i][0])
        {
            sol[poz]=i;
            back(poz+1);
        }
}
int main()
{
    freopen("tricouri.in","r",stdin);
    freopen("tricouri.out","w",stdout);
    read();
    init();
    for(int i=1;i<=m;i++)
    {
        maxim=-1;
        scanf("%d%d",&lung,&baza);
        back(1);
        printf("%d\n",maxim);
    }
    return 0;
}