#include <bits/stdc++.h>
using namespace std;

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

int v[300001], mat[21][20][6], u[21], n, m, nr, p, k, st[6], sk, smax=0, s;

bool suc(){
    if(st[k]>=p-1)
        return 0;

    if(st[k]!=st[k-1]-1){
        sk-=st[k];
        s-=mat[p][st[k]][u[st[k]]];
        u[st[k]]--;
    }
    st[k]++;
    while(st[k]<=p&&u[st[k]]>=mat[p][st[k]][0])
        st[k]++;
    if(st[k]>p) return 0;
    u[st[k]]++;
    s+=mat[p][st[k]][u[st[k]]];
    sk+=st[k];
    return 1;
}

int main(){
    ios::sync_with_stdio(0);
    fin.tie(NULL);
    fout.tie(NULL);

    fin>>n>>m;
    for(int i=1;i<=n;i++)
        fin>>v[i];

    sort(v+1, v+n+1);
    /*for(int i=1;i<=n;i++)
        cout<<v[i]<<' ';
    cout<<endl;*/

    for(int i=n;i>0;i--)
        for(int j=2;j<=20;j++)
            if(mat[j][v[i]%j][0]<5)
                mat[j][v[i]%j][++mat[j][v[i]%j][0]]=v[i];


    /*for(int j=2;j<=20;j++){
        for(int r=0;r<j;r++){
            cout<<j<<' '<<r<<'\n';
            for(int i=1;i<=mat[j][r][0];i++)
                cout<<mat[j][r][i]<<' ';
            cout<<'\n';
        }
    }*/

    for(int q=1;q<=m;q++){
        fin>>nr>>p;
        s=0;
        smax=-1;
        sk=0;
        k=1;
        st[k]=-1;
        //cout<<"nr="<<nr<<" p="<<p<<'\n';
        while(k>0){
            if(k==nr){
                st[k]=p-sk%p;
                if(u[st[k]]<mat[p][st[k]][0]){
                    u[st[k]]++;
                    s+=mat[p][st[k]][u[st[k]]];
                    sk+=st[k];

                    if(s>smax) smax=s;
                    s-=mat[p][st[k]][u[st[k]]];
                    u[st[k]]--;
                    sk-=st[k];
                }
                k--;
            }
            else if(suc()){
                k++;
                st[k]=st[k-1]-1;
            }
            else
                k--;
        }
        fout<<smax<<'\n';
    }
    return 0;
}