#include<bits/stdc++.h>
using namespace std;
ifstream f("tricouri.in");
ofstream g("tricouri.out");
int n,v[300002],m;
bool gut[6][21];
int org[6][21],Ly,R;
struct pp
{
    int l;
    int c;
};
pp fw[6][21];
int main()
{
    f>>n>>m;
    for(int i=1;i<=n;++i)
        f>>v[i];
    sort(v+1,v+n+1,greater<int>());
    for(int i=1;i<=m;++i)
    {
        memset(gut,0,sizeof(gut));
        memset(fw,0,sizeof(fw));
        memset(org,0,sizeof(org));
        f>>Ly>>R; /// I used to
        for(int j=1;j<=n && !gut[Ly][0];++j){
            for(int p=Ly-1;p>=1;--p)
                for(int k=0;k<R;++k)
                    if(gut[p][k] && !gut[p+1][(k+v[j])%R])
                    {
                        gut[p+1][(k+v[j])%R]=1;
                        org[p+1][(k+v[j])%R]=j;
                        fw[p+1][(k+v[j])%R].l=p;
                        fw[p+1][(k+v[j])%R].c=k;
                    }
            if(!gut[1][v[j]%R])
            {
                gut[1][v[j]%R]=1;
                org[1][v[j]%R]=j;
            }
        }
        if(!gut[Ly][0])
            g<<-1<<'\n';
        else
        {
            int B=Ly;
            int J=0;
            int s=0;
            while(B || J)
            {
                s+=v[org[B][J]];
                int a=fw[B][J].l;
                int b=fw[B][J].c;
                B=a;
                J=b;
            }
            g<<s<<'\n'; //g<<"Rose"<<'\n';
        }
    }
    return 0;
}