#include <iostream>
#include <fstream>
using namespace std;

int n,m,d[25][25][6],r[25][6][25];

int main()
{
    ifstream f("tricouri.in");
    ofstream g("tricouri.out");
    f>>n>>m;
    int p,k,val;
    for(int i=0; i<n; ++i) {
        f>>val;
        for(int j=2; j<=20; ++j) {
            k=val%j;
            int bs=val,poz=6;
            for(int l=1; l<6; ++l) if(d[j][k][l]<bs) {
                bs=d[j][k][l];
                poz=l;
            }
            if(6>poz) d[j][k][poz]=val;
        }
    }
    for(int i=2; i<=20; ++i) for(int j=0; j<i; ++j) for(int k=1; k<6; ++k) {
        val=d[i][j][k];
        for(int l=4; 0<=l; --l) for(p=0; p<i; ++p) if(0<l || 0==p)
            r[i][l+1][(p+j)%i]=max(r[i][l+1][(p+j)%i],r[i][l][p]+val);
    }
    for(;m;--m) {
        f>>k>>p;
        if(0==r[p][k][0]) g<<"-1\n";
        else g<<r[p][k][0]<<'\n';
    }
    return 0;
}