#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 sum[6][21],Ly,R,arr[21];
int main()
{
    f>>n>>m;
    for(int i=1;i<=n;++i)
        f>>v[i];
    for(int i=1;i<=m;++i)
    {
        memset(gut,0,sizeof(gut));
        memset(sum,0,sizeof(sum));
        f>>Ly>>R; /// I used to
        for(int j=1;j<=n;++j){
            for(int k=0;k<R;++k)
                arr[k]=(k+v[j])%R;
            for(int p=Ly-1;p>=1;--p)
                for(int k=0;k<R;++k)
                    if(gut[p][k])
                    {
                        gut[p+1][arr[k]]=1;
                        sum[p+1][arr[k]]=max(sum[p+1][arr[k]],sum[p][k]+v[j]);
                    }
            int Rose=v[j]%R;
            sum[1][Rose]=max(sum[1][Rose],v[j]);
            gut[1][Rose]=1;
        }
        if(!gut[Ly][0])
            g<<-1<<'\n';
        else
            g<<sum[Ly][0]<<'\n';  ///g<<"Rose"<<'\n';
    }
    return 0;
}